强制工期相等的双机流水车间排序问题  

Double Machines Flow Workshop Scheduling with Identical Deadline

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

机构地区：[1]暨南大学管理学院,广东广州510632 [2]广东金融学院计算机系,广东广州510520

出　　处：《海南大学学报（自然科学版）》2009年第4期340-345,共6页Natural Science Journal of Hainan University

摘　　要：讨论了强制工期相等的n个工件在双机流水车间的加工.在允许机器空闲的条件下,寻找一个工件排序,使得最大提前完工时间最小.由于工件不允许延迟,问题可能会不可行排序.先讨论问题的可行性,如果问题可行,找出一个可行序列作为预排序列,并给出一个算法计算出每个工件尽可能迟的开工时间,而后,给出一个多项式时间算法,在预排序列的基础上,通过调整最先加工的工件来获得最优排序.In the paper, the problem that n jobs are processed with same deadline in double machines flow shop was discussed. Under the condition of permission the idle insert, a job sequence was determined, which minimize the maximum earliness. Since tardy jobs are prohibited, it is possible that there is no feasible sequence for the problem. Firstly, the feasibility of the sequence was considered. If it is feasible, a sequence used as pre-detennined sequence is founded, and an algorithm to calculate the starting times of job as late as possible was developed. Secondly, based on the pre-determined sequence, a polynomial time algorithm was proposed and optimality was achieved through adjusting the first processing job.

关 键 词：流水车间排序 强制工期 空闲时间 最大提前完工时间 

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