批处理机上具有两类释放时间的工件集竞争调度问题

The Competing Job Sets Scheduling Problems With Two Types of Release Dates on Batching-Machine

研究了两个工件集合竞争在一台批处理机上加工的调度问题,其中每个集合的工件具有一个共同的释放时间.批处理机可以同时加工多个工件作为一批,每批的加工时间为该批工件中加工时间的最大值.基于两类释放时间的大小,针对无界批处理机上最小化一个集合工件的最大完工时间、最大延迟以及总完工时间,使得另一个集合工件的最大完工时间不超过给定上界问题,分别给出了最优求解方法.针对有界批处理机上最小化一个集合工件的最大完工时间,使得另一个集合工件的最大完工时间不超过给定上界问题,证明为一般意义NP-难问题,并给出伪多项式时间最优求解方法.

We consider two sets of jobs competing a single parallel-batching machine where the jobs of each set have a common release date.The parallel-batching machine can process several jobs simultaneously as a batch,and the processing time of a batch is the largest of the job processing times in the batch.Based on the sizes of the two types of release dates,the optimal solutions are presented on minimizing the makespan,the maximum lateness and the total completion time of one set of jobs,respectively,such that the makespan of the other set of jobs is maintained under a xed value on an unbounded batching machine.For the bounded batching machine,minimizing the makespan of one set of jobs sub ject to an upper bound on the makespan of the other set of jobs is proved to be ordinary NP-hard,and pseudo-polynomial time optimal solutions are given.