In the rescheduling on a single machine, a set of the original jobs has already been scheduled, in order to make a given objective function is optimal. The decision maker needs to insert the new jobs into the existing...In the rescheduling on a single machine, a set of the original jobs has already been scheduled, in order to make a given objective function is optimal. The decision maker needs to insert the new jobs into the existing schedule without excessively disrupting it. A batching machine is a machine that can handle up to some jobs simultaneously. In this paper,we consider the total completion time under a limit on the sequence disruptions for parallel batching based on rescheduling. For the parallel batching problem based on rescheduling, we research the properties of feasible schedules and optimal schedules on the total completion time under a limit on the maximum time disruptions or total time disruptions, in which the jobs are sequenced in SPT order, and give out the pseudo-polynomial time algorithms on the number of jobs and the processing time of jobs by applying the dynamic programming method.展开更多
We sttidy the problem of scheduling n jobs on m parallel bounded batch machines to minimize the sum of squared machine loads. Each batch contains at most B jobs, and the processing time of a batch is equal to the long...We sttidy the problem of scheduling n jobs on m parallel bounded batch machines to minimize the sum of squared machine loads. Each batch contains at most B jobs, and the processing time of a batch is equal to the longest processing time of the jobs in this batch. We prove this problem to be NP-hard. Furthermore, we present a polynomial time approximation scheme （PTAS） and a fully polynomial time approximation scheme （FPTAS） for this problem.展开更多
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.展开更多
This paper considers competitive project scheduling on two unbounded parallel batch machines.There are two competing firms,and each firm has an unbounded parallel batch machine.All projects must be performed in batche...This paper considers competitive project scheduling on two unbounded parallel batch machines.There are two competing firms,and each firm has an unbounded parallel batch machine.All projects must be performed in batches by Firms 1 and 2 on their machines,respectively.The profit that each firm obtains from each project depends on whether the firm finishes the job before or after its competitor.In the first problem,given a feasible schedule for Firm 1,the objective is to find an optimal schedule to maximize the total reward for Firm 2 under the given schedule for Firm 1.The corresponding total reward for Firm 1 is called the worst-case total reward of the given schedule for Firm 1.In the second problem,the objective is to find an optimal schedule for Firm 1 to maximize the worst-case total reward.We provide optimal algorithms for the two problems,respectively.展开更多
基金Supported by the National Natural Science Foundation of China（11271338, 11201121, 71201049） Supported by the National Natural Science Foundation of Henan Province（112300410078） Supported by the Natural Science Foundation of the Education Department of Henan Province（2011B110008）
文摘In the rescheduling on a single machine, a set of the original jobs has already been scheduled, in order to make a given objective function is optimal. The decision maker needs to insert the new jobs into the existing schedule without excessively disrupting it. A batching machine is a machine that can handle up to some jobs simultaneously. In this paper,we consider the total completion time under a limit on the sequence disruptions for parallel batching based on rescheduling. For the parallel batching problem based on rescheduling, we research the properties of feasible schedules and optimal schedules on the total completion time under a limit on the maximum time disruptions or total time disruptions, in which the jobs are sequenced in SPT order, and give out the pseudo-polynomial time algorithms on the number of jobs and the processing time of jobs by applying the dynamic programming method.
文摘We sttidy the problem of scheduling n jobs on m parallel bounded batch machines to minimize the sum of squared machine loads. Each batch contains at most B jobs, and the processing time of a batch is equal to the longest processing time of the jobs in this batch. We prove this problem to be NP-hard. Furthermore, we present a polynomial time approximation scheme （PTAS） and a fully polynomial time approximation scheme （FPTAS） for this problem.
基金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.
基金This research was supported in part by the National Natural Science Foundation of China(Nos.11771406,11571321 and U1504103).
文摘This paper considers competitive project scheduling on two unbounded parallel batch machines.There are two competing firms,and each firm has an unbounded parallel batch machine.All projects must be performed in batches by Firms 1 and 2 on their machines,respectively.The profit that each firm obtains from each project depends on whether the firm finishes the job before or after its competitor.In the first problem,given a feasible schedule for Firm 1,the objective is to find an optimal schedule to maximize the total reward for Firm 2 under the given schedule for Firm 1.The corresponding total reward for Firm 1 is called the worst-case total reward of the given schedule for Firm 1.In the second problem,the objective is to find an optimal schedule for Firm 1 to maximize the worst-case total reward.We provide optimal algorithms for the two problems,respectively.
