| 部分工件必须不误工的误工排序问题 |
| |
| 引用本文： | 彭洪洁,苏永英,唐国春.部分工件必须不误工的误工排序问题[J].重庆师范大学学报(自然科学版),2009,26(2):18-21. |
| |
| 作者姓名： | 彭洪洁 苏永英 唐国春 |
| |
| 作者单位： | 1. 重庆师范大学,数学与计算机科学学院,重庆,400047
2. 重庆师范大学,数学与计算机科学学院,重庆,400047;上海第二工业大学,管理工程研究所,上海,201209 |
| |
| 基金项目： | 国家自然科学基金，运筹学与系统工程重庆市市级重点实验室资助项目 |
| |
| 摘 要： | 排序论中使误工工件的个数为最少的单台机器排序问题,称为误工问题,是排序论中最基本的问题之一.1973年,Sidney研究在工件的一个子集T中的工件必须不误工的条件下,使误工工件的个数为最少的误工排序问题1｜T｜∑Uj,并且给出该问题复杂性为O(n log n)的多项式算法--Sidney算法.本文把Sidney 算法改写成比较简洁的算法1,1)步骤1:设E 0=T,J－E 0=｛j1,j2,…,jm｝,j1＜j2＜…＜jm,m=n-｜T｜,令k=1:2)步骤2:若k=m+1,算法终止,(Em,J－Em)就是最优排序:若k＜m+1,转入步骤3:3)步骤3:设Fk=Ek-1∪{jk},计算Ek如下:如果Fk是不误工子集,令Ek=Ek-1∪{jk}:否则,如果Fk不是不误工子集,令Ek+Fk\{jr}.其中工件jr的加工时间为pr=max{pi｜ji∈Fk\T}.Ek中的工件是按EDD序排列.k=k+1,转入步骤2.并用数学归纳法证明算法1产生的排序是该误工问题的最优解.
|
| 关 键 词： | 排序 误工 算法 最优性 |
Minimizing the Number of Tardy jobs with a Subset T of the jobs which must be on Time |
| |
| PENG Hong-jie,SU Yong-ying,TANG Guo-chun.Minimizing the Number of Tardy jobs with a Subset T of the jobs which must be on Time[J].Journal of Chongqing Normal University:Natural Science Edition,2009,26(2):18-21. |
| |
| Authors: | PENG Hong-jie SU Yong-ying TANG Guo-chun |
| |
| Institution: | 1.College of Mathematics and Computer Science;Chongqing Normal University;Chongqing 400047;2.Institute of Management Engineering;Shanghai Second Polytechnic University;Shanghai 201209;China |
| |
| Abstract: | |
| |
| Keywords: | scheduling tardy jobs algorithm optimality |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《重庆师范大学学报(自然科学版)》浏览原始摘要信息 |
| 点击此处可从《重庆师范大学学报(自然科学版)》下载免费的PDF全文 |
|
