带准备时间和强制工期的单机排序问题  

Single machine scheduling with ready times and deadlines

作　　者：钟雪灵[1,2] 王国庆[1] 王雄志[3] 

机构地区：[1]暨南大学管理学院,广东广州510632 [2]广东金融学院计算机系,广东广州510520 [3]华南农业大学经济管理学院,广东广州510642

出　　处：《暨南大学学报（自然科学与医学版）》2010年第3期273-276,共4页Journal of Jinan University(Natural Science & Medicine Edition)

基　　金：教育部人文社会科学研究项目(09YJC630088)

摘　　要：讨论了带准备时间和强制工期的单机排序问题.在工件可中断、机器可空闲的条件下,确定一个工件排序,使得最大提前完工时间最小.由于工件不允许延迟,首先考虑了问题的可行性.通过将问题转化为一个带容量限制的有向图,并运用求解最大网络流的算法,提出了判定问题可行性的方法.对于可行问题,给出了一个算法在多项式时间内获得最优排序.This paper discusses the scheduling problem that jobs with ready times and deadlines have to be processed on a single machine.The objective is to find a preemptive job sequence so as to minimize the maximum earliness considering the idle insert.Since tardy jobs are prohibited,we consider the feasibility primarily.The method of determining the feasibility is proposed through transforming the problem to a corresponding directed graph with capacity constraint,and adopting the algorithm of solving maximum network flow problem.A polynomial time algorithm is developed to achieve optimality for the feasible problem.

关 键 词：单机排序 准备时间 强制工期 空闲时间 最大提前完工时间 

分 类 号：O223[理学—运筹学与控制论]