带强制工期的双机开放车间排序问题  

Two Machines Open Shop Scheduling with Identical Deadline

作　　者：钟雪灵[1] 王国庆[2] 程明宝[3] 李晓春[4] 

机构地区：[1]广东金融学院计算机系,广东广州510520 [2]暨南大学管理学院,广东广州510632 [3]广东工业大学管理学院,广东广州510520 [4]华南师范大学南海校区,广东南海528225

出　　处：《运筹与管理》2011年第4期108-112,共5页Operations Research and Management Science

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

摘　　要：讨论了强制工期相等的n个工件在双机开放车间加工。在允许机器空闲的条件下,寻找一个工件排序,使得最大提前完工时间最小。由于工件不允许延迟,问题可能会无可行排序。先讨论了问题的可行性。如果问题可行,找出一个可行序列作为预排序列,并提出了一个算法计算每个工件尽可能迟的开工时间。而后,提出了一个多项式时间最优算法,在预排序列的基础上,通过调整两台机器上最先加工的工件来获得最优排序。This paper discusses the problem in which n jobs with common deadline have to be processed on two machines open shop considering the idle insert.The objective is to find a job sequence and determine jobs＇ starting times so as to minimize the maximum earliness.Since tardy jobs are prohibited,it＇s possible that there is no feasible sequence for the problem.We consider the feasibility primarily.If the problem is feasible,we first pre-determine a sequence and develop an algorithm to compute jobs＇ starting times to make jobs process as late as possible.Then,a polynomial time algorithm is developed to achieve optimality through adjusting the first processing job on the two machines based on the pre-determined sequence.

关 键 词：运筹学 排序 开放车间 强制工期 最大提前完工时间 

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