东北大学学报（自然科学版）

东北大学学报:自然科学版 ›› 2014, Vol. 35 ›› Issue (9): 1329-1334.DOI: 10.12068/j.issn.1005-3026.2014.09.026

• 机械工程 • 上一篇    下一篇

求解带缓冲区和机器可用性约束的非置换流水车间调度

郑永前，李燕   

  1. (同济大学 机械与能源工程学院， 上海201804)
  • 收稿日期:2013-07-12 修回日期:2013-07-12 出版日期:2014-09-15 发布日期:2014-04-11
  • 通讯作者: 郑永前
  • 作者简介:郑永前(1965-)，男，河南商丘人，同济大学副教授.
  • 基金资助:
    国家自然科学基金资助项目(71071115，61273035).

Solution for Nonpermutation Flow Shop Scheduling with Buffers and Machine Availability Constraints

ZHENG Yongqian， LI Yan   

  1. School of Mechanical Engineering， Tongji University， Shanghai 201804， China.
  • Received:2013-07-12 Revised:2013-07-12 Online:2014-09-15 Published:2014-04-11
  • Contact: LI Yan
  • About author:-
  • Supported by:
    -

RichHTML

0

PDF (PC)

666

摘要： 为得到非置换流水车间更好的调度方案，考虑到缓冲区、机器可用性约束和序列相关换模时间，以最小化最大完工时间为目标，建立数学模型和析取图模型，构造了一种面向NPFS的列表启发式算法.算法通过允许列表和候选列表记录启发式过程信息，采用量子蚁群和SPT启发式规则搜索并选择析取边的可行移动方案，得到一个没有冲突的有向非循环图.通过正交试验法验证了算法关键参数，实例验证了算法求解和CPLEX的精确解相同.同时采用8组Demirkol测试问题，与MHD-ACS和ACO算法比较评估，验证了算法的有效性和鲁棒性.

关键词: 缓冲区, 非置换, 机器可用性, 析取图, 量子蚁群

Abstract: To get a better nonpermutation flow shop(NPFS) scheduling， buffers， machine availability constraints and sequencedependent setup time were considered in building the mathematical model and disjunctive graph model. A NPFSoriented list heuristic algorithm was constructed to minimize the makespan. Allowed list and candidate list were built to record heuristic process information. Quantum ant colony and SPT heuristic rule were applied to search and select the feasible movement of related disjunction arcs to get an acyclic conjunctive graph. The algorithm parameters were verified through orthogonal test. The optimal disjunctive scheduling solution was the same with the exact CPLEX solution. The proposed algorithm has been critically compared and assessed by eight benchmark problems from Demirkol with the MHDACS and ACO ones， which confirms its good effectiveness and robustness.

Key words: buffers, nonpermutation, machine availability, disjunctive graph, quantum ant colony

中图分类号: