«上一篇/Previous Article|本期目录/Table of Contents|下一篇/Next Article»

重庆师范大学学报（自然科学版）[ISSN:1672-6693/CN:50-1165/N]

卷:

26

期数:

2009年02期

页码:

1-6

栏目:

运筹学与控制论

出版日期:

2009-04-25

文章信息/Info

Title:

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

作者:

唐　国　春

1．上海第二工业大学 管理工程研究所，上海201209; 2．重庆师范大学 数学与计算机科学学院，重庆400047

Author(s):

TANG Guo-chun1; 2

1. Institute of Management Engineering, Shanghai Second Polytechnic University, Shanghai 200041;
2. College of Mathematics and Computer Science, Chongqing Normal University, Chongqing 400047, China

关键词:

排序; 误工; 算法; 最优性

Keywords:

-

分类号:

-

DOI:

10.11721/cqnuj20090201

文献标志码:

A

摘要:

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

Abstract:

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 profound results were 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)|∑wjUj 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.

参考文献/References:

-

备注/Memo

备注/Memo:

-

常用功能

更新日期/Last Update: 2009-06-04