具有机器适用限制的分布式置换流水车间问题的模型与算法  

Model and algorithms of the distributed permutation flow shop scheduling problem with machine eligibility constraints

作　　者：蔡爽 杨珂 刘克[1] CAI Shuang;YANG Ke;LIU Ke(Academy of Mathematics and Systems Science,Chinese Academy of Sciences,Beijing 100190,China)

机构地区：[1]中国科学院数学与系统科学研究院,北京100190

出　　处：《运筹学学报》2018年第4期17-30,共14页Operations Research Transactions

基　　金：国家自然科学基金(No.71390334)

摘　　要：考虑具有机器适用限制的多个不同置换流水车间的调度问题.机器适用限制指的是每个工件只能分配到其可加工工厂集合.所有置换流水车间拥有的机器数相同但是具有不同的加工能力.首先,针对该问题建立了基于位置的混合整数线性规划模型;进而,对一般情况和三种特殊情况给出了具有较小近似比的多项式时间算法.其次,基于NEH方法提出了启发式算法NEHg,并给出了以NEHg为上界的分支定界算法.最后,通过例子说明了NEHg启发式算法和分支定界算法的计算过程,并进行大量的实验将NEHg与NEH算法结果进行比较,从而验证了NEHg算法的有效性.This paper considers the distributed permutation flow shop scheduling problem with eligibility constraints,which means that there exists an available factory set for each job.The processing time of each job in different factories may not be the same.We present a mixed integer linear programming based on position of jobs in all factories.The general problem and three special cases are analyzed and several heuristic algorithms are proposed with performance guarantee.A heuristic algorithm based on greedy algorithm,LFJ and NEH is carried out to obtain an approximate solution.The branch and bound method based on the approximate value is proposed to find optimal scheduling.At last,an example is used to explain the computing process of NEHg2 and the branch and bound method;numerous experiments prove the effectiveness of the NEHg heuristics.

关 键 词：分布式置换流水车间 机器适用限制 混合整数线性规划模型 启发式算法 分支定界算法 

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