等待时间受限的置换流水车间调度启发式算法

针对等待时间受限的置换流水车间调度问题,分析了其可行解与流水车间调度最优解的关系,给出了计算最大完工时间的有向图,证明了等待时间受限的置换流水车间调度问题的可逆性,并以此为基础提出了一种启发式算法.算法首先根据等待时间受限约束与无等待(no-wait)约束的相似特征,生成初始工件序列集;然后利用问题可逆性给出了复杂度为O(n2m)的插入优化机制,进一步优化初始解.数据实验的结果验证了启发式算法的可行性和有效性.

Heuristic algorithm for permutation flowshop scheduling problem with limited waiting time constraints

The permutation flowshop scheduling problem with limited waiting time constraints is studied.The relationship between permutation schedules and optimal solutions of the corresponding flowshop scheduling are analyzed.With the discussion of the directed graph for the makespan computation of a permutaiton schedule,the reversibility of permutation flowshop scheuduling with limited waiting time constraints is proved.Based on these properties,a heuristic algorithm is proposed.In the algorithm,an initial set of job permutations are obtained based on the similar characteristics to the no-wait constraints.Then,an inserting optimization mechanism,which can be done in O(n2m) time by the reversibility of the problem,is introduced to improve the initial schedules.Numerical results demonstrate the fesibility and effectiveness of the algorithm.