部分工件必须不误工的误工排序问题-重庆师范大学学报（自然科学版）

文章信息/Info

Title:: Minimizing the Number of Tardy jobs with a Subset T of the jobs which must be on Time

作者:: 彭洪洁1; 苏永英1; 唐国春1; 2; 1. 重庆师范大学数学与计算机科学学院, 重庆 400047；2. 上海第二工业大学管理工程研究所，上海 201209

Author(s):: PENG Hong-jie1; SU Yong-ying1; TANG Guo-chun1; 2; 1.College of Mathematics and Computer Science, Chongqing Normal University, Chongqing 400047；
2.Institute of Management Engineering, Shanghai Second Polytechnic University, Shanghai 201209，China

摘要:: 排序论中使误工工件的个数为最少的单台机器排序问题，称为误工问题，是排序论中最基本的问题之一。1973年，Sidney研究在工件的一个子集T中的工件必须不误工的条件下，使误工工件的个数为最少的误工排序问题1∣T∣∑Uj，并且给出该问题复杂性为O(n log n)的多项式算法——Sidney算法。本文把Sidney算法改写成比较简洁的算法1，1) 步骤1：设E0＝T，J－E0＝{j1 , j2 , …, jm}，j1< j2<…< jm，m＝n－∣T∣，令k＝1；2) 步骤2：若k＝m+1，算法终止，（Em，J－Em）就是最优排序；若k

Abstract:: The single machine scheduling problem to minimize the number of tardy jobs is one of the most basic scheduling problems in scheduling theory. In 1973, Sidney studied the scheduling problem 1∣T∣∑Uj to minimize the number of tardy jobs with a subset T of the jobs which must be on time and give a polynomial time algorithm to solve this problem, the optimal could be gotten in time O(n log n). This algorithm is called Sidney Algorithm by scholars in the following years. In this paper, we revised Sidney Algorithm as following: Step1: Suppose E0＝T, J－E0＝{j1 , j2 , …, jm}, j1< j2<…< jm, m＝n－∣T∣, let k＝1; Step2: If k＝m+1, stop, then the schedule（Em，J－Em） is optimal; Else turn to step3; Step3: Arrange the jobs according to the earliest due date (EDD) schedule in Ek , assume Fk＝Ek-1∪{jk}, if Fk is a tardy subset, let Ek＝Ek-1∪{jk}; else Ek＝Fk\{jr},where the processing time of job jr satisfying: pr＝max{ pi∣ji?Fk\T }. Let k=k+1, turn to step2. In the end, we use induction to prove the schedule got from the revised algorithm is also an optimal solution for this problem.