单机分批不相容排序问题

Incompatible Scheduling Problem on Single Batch Machine

该文考虑的是n个任务在一台平行分批处理机上加工的排序问题,任务被分成两类不相容的任务集,不相容任务集的任务不能放在同一批中加工,目标函数是极小化时间表长和总完工时间,我们先利用DP算法找到第二类任务集的最优批排序,然后利用修改过的WSPT规则在o（n22）时间内找到整个排序问题的最优算法。

In this paper we consider the scheduling problem for n jobs on a single parallel batch processing machine-jobs are divided into two incompatible task sets,whose task can not be processed in the same batch.The objective function is the minimization of the makespan and total completion time. First,we use the DP algorithm to find the optimal batch schedule of the second type of task set,and then,we use the modified WSPT rules to find the optimal algorithm of the scheduling problem in o（n22） time.