This paper considers a reclaimer scheduling problem in which one has to collect bulk material from stockpiles in the quay in such a way that the time used is minimized. When reclaimers are allowed to work on the same ...This paper considers a reclaimer scheduling problem in which one has to collect bulk material from stockpiles in the quay in such a way that the time used is minimized. When reclaimers are allowed to work on the same stockpile simultaneously, a fully polynomial time approximation scheme（FPTAS） is designed. Further,we present a 2-approximation algorithm in the case that any stockpile can be handled by only one reclaimer at a time. When the number of reclaimers is two, we give a 3/2-approximation algorithm. Numerical experiments show that the algorithms perform much better than our worst case analysis guarantees.展开更多
The online scheduling on an unbounded parallel batch machine with delivery times and limited restarts is studied in this paper.Here,online means that jobs arrive over time and the characteristics of a job become known...The online scheduling on an unbounded parallel batch machine with delivery times and limited restarts is studied in this paper.Here,online means that jobs arrive over time and the characteristics of a job become known until it arrives.Limited restarts mean that once a running batch contains at least one restarted job,it cannot be restarted again.The goal is to minimize the time by which all jobs have been delivered.We consider a restricted model that the delivery time of each job is no more than its processing time.We present a best possible online algorithm with a competitive ratio of 3/2 for the problem.展开更多
Two-agent single-machine scheduling problem is considered in this paper.Agent A’s goal is to minimize the sum of the total weighted delivery time and the total delivery cost,and agent B has the delivery time window.F...Two-agent single-machine scheduling problem is considered in this paper.Agent A’s goal is to minimize the sum of the total weighted delivery time and the total delivery cost,and agent B has the delivery time window.First,the NP-hardness of the general problem is proved,and then two special cases are considered.One case is that A’s jobs have agreeable ratio and this problem is still NP-hard.A pseudo-polynomial dynamic programming algorithm and a 32-approximation algorithm are designed.In the other case,A’s jobs have agreeable ratio and B’s jobs have deadline at the same time.This problem is polynomial solvable.展开更多
基金Supported by the National Natural Science Foundation of China(No.11371137 and No.71431004)
文摘This paper considers a reclaimer scheduling problem in which one has to collect bulk material from stockpiles in the quay in such a way that the time used is minimized. When reclaimers are allowed to work on the same stockpile simultaneously, a fully polynomial time approximation scheme（FPTAS） is designed. Further,we present a 2-approximation algorithm in the case that any stockpile can be handled by only one reclaimer at a time. When the number of reclaimers is two, we give a 3/2-approximation algorithm. Numerical experiments show that the algorithms perform much better than our worst case analysis guarantees.
基金This research was supported by the National Natural Science Foundation of China(Nos.11701148,11871213 and 11571321)Henan University of Engineering(No.D2016017).
文摘The online scheduling on an unbounded parallel batch machine with delivery times and limited restarts is studied in this paper.Here,online means that jobs arrive over time and the characteristics of a job become known until it arrives.Limited restarts mean that once a running batch contains at least one restarted job,it cannot be restarted again.The goal is to minimize the time by which all jobs have been delivered.We consider a restricted model that the delivery time of each job is no more than its processing time.We present a best possible online algorithm with a competitive ratio of 3/2 for the problem.
基金the National Natural Science Foundation of China(No.11371137)。
文摘Two-agent single-machine scheduling problem is considered in this paper.Agent A’s goal is to minimize the sum of the total weighted delivery time and the total delivery cost,and agent B has the delivery time window.First,the NP-hardness of the general problem is proved,and then two special cases are considered.One case is that A’s jobs have agreeable ratio and this problem is still NP-hard.A pseudo-polynomial dynamic programming algorithm and a 32-approximation algorithm are designed.In the other case,A’s jobs have agreeable ratio and B’s jobs have deadline at the same time.This problem is polynomial solvable.
