|本期目录/Table of Contents|

[1]刘朝晖.批处理机上有就绪和截止时间的等长度工件排序[J].重庆师范大学学报(自然科学版),2009,26(03):1-004.[doi:10.11721/cqnuj20090330]
　LIU Zhao-hui.Scheduling Equal-length Jobs with Release Times and Deadlines on a Batch Machine[J].期刊社,2009,26(03):1-004.[doi:10.11721/cqnuj20090330]
点击复制

批处理机上有就绪和截止时间的等长度工件排序(PDF)
分享到：

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

卷:
26
期数:
2009年03期
页码:
1-004
栏目:
运筹学与控制论
出版日期:
2009-07-14

文章信息/Info

Title:
Scheduling Equal-length Jobs with Release Times and Deadlines on a Batch Machine
作者:
刘朝晖
华东理工大学数学系，上海200237
Author(s):
LIU Zhao-hui
关键词:
排序; 批处理机; 等长度工件; 多项式时间算法
Keywords:
-
分类号:
-
DOI:
10.11721/cqnuj20090330
文献标志码:
A
摘要:

一台批处理机一次可以同时加工多个工件（称为一批），每批工件有相同的开工和完工时间，加工时间等于其中最长工件的加工时间。本文研究单台批处理机上有就绪时间和截止时间约束的n个等长度工件的排序问题，目标是求一个可行时间表。就该问题，Baptiste已经提出了一个复杂性为O（n8）的算法，在此基础上，本文推广Garey等人关于对应的经典排序问题的算法，得到了一个复杂性为O（n2）的算法。算法分两个阶段执行：在阶段I，算法找出所谓的禁止开工区间，在这些区间中将不允许有工件开工；在阶段II，算法从时刻零开始，每当机器有空闲且不属于禁止开工区间的时候，就按照最早截止时间优先规则从已就绪的未加工工件中选择尽可能多的工件作为一批进行加工，若当前的机器空闲时刻属于某个禁止开工区间，则首先更新其到该禁止开工区间的右端点再进行决策。

Abstract:

参考文献/References:

-

备注/Memo

备注/Memo:
-
更新日期/Last Update: 2009-07-07