误工排序问题的研究
作者:
作者单位:

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

作者简介:

通讯作者:

基金项目:


A Study of Scheduling Problems to Minimize the Number of Tardy Jobs
Author:
Affiliation:

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

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
    摘要:

    误工排序问题是经典排序论中最基本和最重要的问题。四十年来国内外许多学者对其进行研究的兴趣有增无减,深刻的成果不断涌现。本文阐述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.

    参考文献
    相似文献
    引证文献
引用本文

唐国 春.误工排序问题的研究[J].重庆师范大学学报自然科学版,2009,(2):1-6

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
历史
  • 收稿日期:
  • 最后修改日期:
  • 录用日期:
  • 在线发布日期: