部分工件必须不误工的误工排序问题
作者:
作者单位:

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

作者简介:

通讯作者:

基金项目:


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

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

Fund Project:

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

    排序论中使误工工件的个数为最少的单台机器排序问题,称为误工问题,是排序论中最基本的问题之一。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.

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

彭洪洁,苏永英,唐国春.部分工件必须不误工的误工排序问题[J].重庆师范大学学报自然科学版,2009,(2):18-21

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