工件具有子工件工期的排序问题

Scheduling with sub-jobs' due dates

研究了工件具有子工件工期的排序问题.需要在一台单机上加工若干个给定的工件.每个工件由若干个子工件组成,每个子工件都有各自的工期.只有当工件的每个子工件都按时完成,才能称该工件是按时完工工件,否则,称该工件产生延误.目标是最大化按时完工的工件个数.证明当每个工件都被分成两个子工件时,该问题是NP-难的,而且不存在完全多项式时间近似方案(fully polynomial time approximation scheme,简记为FPTAS).提出两个启发式算法,利用数值模拟比较它们的性能,并且将这两个启发式算法的解与最优解的上界进行比较.

In this paper,we study a single machine scheduling problem in which sub-jobs have due dates.Given a set of jobs,each job is divided into several sub-jobs and each sub-job has a due date.A job is completed on time only if all its sub-jobs are completed before their due dates.We prove that even if each job has two sub-jobs,this problem is NP-hard and there is no FPTAS for this special case.Furthermore,we propose two heuristics for this model and a heuristic to get an upper bound and carry out numerical experiments to compare their performances.