工件具有子工件工期的排序问题
|
摘要
研究了工件具有子工件工期的排序问题.需要在一台单机上加工若干个给定的工件.每个工件由若干个子工件组成,每个子工件都有各自的工期.只有当工件的每个子工件都按时完成,才能称该工件是按时完工工件,否则,称该工件产生延误.目标是最大化按时完工的工件个数.证明当每个工件都被分成两个子工件时,该问题是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.
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.
引文
[1] Moore J M. An job, one machine sequencing algorithm for minimizing the number of late jobs[J]. Management Science, 1968, 15:102-109.
[2] Lenstra J K, Kan Rinnooy A H G, Brucker P. Complexity of machine scheduling problems[J].Annals of Discrete Mathematics,1977, 1:343-362.
[3] Stephane D P, Sevaux M. An exact method to minimize the number of tardy jobs in single machine scheduling[J]. Journal of Scheduling,2004, 7:405-420.
[4] Chen B, Potts C N, Strusevich V A. Approximation algorithms for two-machine flow shop scheduling with batch setup times[J]. Mathematical Programming, 1998, 82:255-271.
[5] Gong H, Tang L, Leung J Y T. Parallel machine scheduling with batch deliveries to minimize total flow time and delivery cost[J]. Naval Research Logistics, 2016, 63:492-502.
[6] Liu L L, Ng C T, Cheng T C E. On the complexity of bi-criteria scheduling on a single batch processing machine[J]. Journal of Scheduling, 2010, 13, 629-638.
[7] Liu Z, Yuan J, Cheng T C E. On scheduling an unbounded batch machine[J]. Operations Research Letters, 2003, 31, 42-48.
[8] Garey M R.,.Johnson D S. Computers and Intractability:A Guide to the Theory of NPCompleteness[M]. New York:Freeman, 1979.
[9] Woeginger G J. When does a dynamic programming formulation guarantee the existence of a fully polynomial time approximation scheme(FPTAS)?[J]. Informs Journal on Computing,2000, 12:57-74.
[2] Lenstra J K, Kan Rinnooy A H G, Brucker P. Complexity of machine scheduling problems[J].Annals of Discrete Mathematics,1977, 1:343-362.
[3] Stephane D P, Sevaux M. An exact method to minimize the number of tardy jobs in single machine scheduling[J]. Journal of Scheduling,2004, 7:405-420.
[4] Chen B, Potts C N, Strusevich V A. Approximation algorithms for two-machine flow shop scheduling with batch setup times[J]. Mathematical Programming, 1998, 82:255-271.
[5] Gong H, Tang L, Leung J Y T. Parallel machine scheduling with batch deliveries to minimize total flow time and delivery cost[J]. Naval Research Logistics, 2016, 63:492-502.
[6] Liu L L, Ng C T, Cheng T C E. On the complexity of bi-criteria scheduling on a single batch processing machine[J]. Journal of Scheduling, 2010, 13, 629-638.
[7] Liu Z, Yuan J, Cheng T C E. On scheduling an unbounded batch machine[J]. Operations Research Letters, 2003, 31, 42-48.
[8] Garey M R.,.Johnson D S. Computers and Intractability:A Guide to the Theory of NPCompleteness[M]. New York:Freeman, 1979.
[9] Woeginger G J. When does a dynamic programming formulation guarantee the existence of a fully polynomial time approximation scheme(FPTAS)?[J]. Informs Journal on Computing,2000, 12:57-74.