English

运筹学学报

• 运筹学 • 上一篇    下一篇

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

蔡爽1,*  杨珂1  刘克1   

  1. 1. 中国科学院数学与系统科学研究院, 北京 100190
  • 收稿日期:2017-05-08 出版日期:2018-12-15 发布日期:2018-12-15
  • 通讯作者: 蔡爽 E-mail: caishuang@amss.ac.cn
  • 基金资助:

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

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

CAI Shuang1,*  YANG Ke1   LIU Ke1   

  1. 1. Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China
  • Received:2017-05-08 Online:2018-12-15 Published:2018-12-15

PDF

325

摘要：

考虑具有机器适用限制的多个不同置换流水车间的调度问题. 机器适用限制指的是每个工件只能分配到其可加工工厂集合. 所有置换流水车间拥有的机器数相同但是具有不同的加工能力. 首先, 针对该问题建立了基于位置的混合整数线性规划模型; 进而, 对一般情况和三种特殊情况给出了具有较小近似比的多项式时间算法. 其次, 基于NEH方法提出了启发式算法NEHg, 并给出了以NEHg为上界的分支定界算法. 最后, 通过例子说明了NEHg启发式算法和分支定界算法的计算过程, 并进行大量的实验将NEHg与NEH算法结果进行比较, 从而验证了NEHg算法的有效性.

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

Abstract:

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.

Key words: distributed permutation flow shop scheduling, machine eligibility constraints, mathematic programming, heuristic algorithm, branch and bound method