误工排序问题的研究

A Study of Scheduling Problems to Minimize the Number of Tardy Jobs

误工排序问题是经典排序论中最基本和最重要的问题。40年来国内外许多学者对其进行研究的兴趣有增无减,深刻的成果不断涌现。本文阐述2006年以来重庆师范大学运筹学与控制论专业的硕士研究生在研究误工排序问题上得到的成果及其意义。这些成果包括研究经典的和推广的误工问题,包括某些工件必须不误工,或者工件的就绪时间不相同、与交货期有一致性的,或者带权的误工排序问题,或者工件的加工时间与工件的权有反向一致性,或者多台平行机误工排序问题等等得到的成果。

The single machine scheduling problem to minimize the number of tardy jobs is one of the most basic and important scheduling problems in classical scheduling theory. An algorithm of Moore, which is sometimes known as the Moore-Hodgson algorithm, solves the problem in O（n log n） time. This algorithm repeatedly adds jobs in EDD order to the end of a partial schedule of on-time jobs. If the addition of job j results in this job completed after time dj, then a job in the partial schedule with the largest processing time is removed and declared late. Discarding a job with the largest processing time increases the opportunity for subsequent jobs to be completed by their due dates. In the past 40 years, lots of researchers studied it with ever-increasing interests and their profound results appeared continually. For example, Sidney generalizes this algorithm to handle the case that a specified subset of jobs must be on time. He observes that jobs of the specified subset are not considered when discarding jobs, and that it may be necessary to discard more than one job to ensure that the last job in the current partial schedule is on time. Adaptations of Moore-Hodgson＇s algorithm to both problem 1 ｜ （ ri ≤ rj ） → （ di ≤ dj ） ｜ ∑ Uj and problem 1 ｜ （pi ≤ pj） → （ wi ≥ wj ） ｜ ∑ wj Uj for the cases of both agreeability of release dates with due dates, and reverse agreeability of processing times with weights are proposed by both Kise, Ibaraki and Mine, and Lawler, respectively. In this paper we review results and their significances on the problems obtained by master students in Chongqing Normal University, including classical ones and their generalizations.