Please wait a minute...
浙江大学学报(工学版)
浙江大学学报(工学版)
机械工程     
多阶段可替换分组并行机调度问题的求解
苗峰1,谢安桓1,王富安2,喻峰2,周华1
1.浙江大学 流体动力与机电系统国家重点实验室,浙江 杭州 310027；2.中国船舶重工集团第七〇七研究所九江分部,江西 九江 332007
Method for multi-stage alternative grouping parallel machines scheduling problem
MIAO Feng1, XIE An-huan1, WANG Fu-an2, YU Feng2, ZHOU Hua1
1. State Key Laboratory of Fluid Power Transmission and Control, Zhejiang University, Hangzhou 310027, China; 2.Jiujiang Branch of 707 Research Institute of CSIC, Jiujiang 332007, China
 全文: PDF(811 KB)   HTML
摘要：
针对一类多阶段可替换分组并行机混流生产调度问题,以最小化最大完工时间为目标建立问题的数学模型,提出一种嵌入混合启发规则的遗传算法,采用分段独立编码的染色体和改进的遗传算子.依靠遗传算法的全局搜索能力确定启发规则的最优决策变量,根据决策变量采用包含多种规则的混合规则确定各阶段调度方案；同时解决了调度问题的路径选择子问题和加工排序子问题,调度方案自动满足模型约束.算法求解速度快,求解结果具有较高的负荷平衡率.针对不同规模的算例,仿真验证了算法的有效性,仿真结果表明该算法的综合性能指标优于嵌入单一启发规则的遗传算法.
Abstract:
To solve the mixed flow scheduling problem with multi-stage alternative grouping parallel machines, the mathematical model to minimize the maximum completion time was constructed and a hybrid heuristic-genetic algorithm was developed, the algorithm bases on piecewise independent coding method and modified genetic operators. The optimal decision variables of scheduling rules is determined by the global search ability of genetic algorithm. Scheduling scheme of each stage is determined by using the decision variables and the hybrid heuristic rules which contains a variety of scheduling rules. The algorithm can solve path selection sub-problems and processing sorting sub-problems at the same time, and the results automatically satisfy model constraints. This algorithm has following advantages: high arithmetic speed, optimum results taking into higher rates of load-balancing and etc. Simulation examples of different scales verify the effectiveness of the algorithm. The comparison indicates that the composite indicator of this algorithm is superior to that of single heuristic-genetic algorithms．
出版日期: 2015-12-26
:  TP 18  
基金资助:

国家自然科学基金创新研究群体科学基金资助项目（51221004）
通讯作者: 周华，男，教授，博导     E-mail: zhouh@cmee.zju.edu.cn
作者简介: 苗峰（1990- ），男，硕士生，主要从事生产线设计与调度的相关研究. E-mail:miaofeng646@zju.edu.cn
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　

引用本文:

苗峰,谢安桓,王富安,喻峰,周华. 多阶段可替换分组并行机调度问题的求解[J]. 浙江大学学报(工学版), 10.3785/j.issn.1008-973X.2015.05.008.

MIAO Feng, XIE An-huan, WANG Fu-an, YU Feng, ZHOU Hua. Method for multi-stage alternative grouping parallel machines scheduling problem. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 10.3785/j.issn.1008-973X.2015.05.008.

链接本文:

http://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2015.05.008    或    http://www.zjujournals.com/eng/CN/Y2015/V49/I5/866

［1］ 刘志雄, 王少梅. 基于粒子群算法的并行多机调度问题研究［J］. 计算机集成制造系统, 2006, 12(2): 183-187．
LIU Zhi-xiong, WANG Shao-mei. Research on parallel machines scheduling problem based on particle swarm optimization algorithm ［J］. Computer Integrated Manufacturing Systems, 2006, 12(2): 183-187．
［2］ 贺仁杰, 谭跃进. 具有时间窗口约束的并行机床调度问题研究［J］. 系统工程, 2004, 22(5): 18-22．
HE Ren-jie, TAN Yue-jin. On parallel machine scheduling problem with time windows ［J］. Systems Engineering, 2004, 22(5): 18-22．
［3］ 胡大勇, 姚振强. 调整时间与顺序相关的等同并行机调度［J］. 机械工程学报, 2011, 47(16): 160-165．
HU Da-yong, YAO Zhen-qiang. Identical parallel machines scheduling with sequence-dependent setup times ［J］. Journal of Mechanical Engineering, 2011, 47(16): 160-165．
［4］ GUPTA J N D. Two-stage hybrid flow shop scheduling problem ［J］. Journal of the Operational Research Society, 1988, 39(4): 359-364．
［5］ OGUZ C, LIN B M T, EDWIN C T C. Two-stage flow shop scheduling with a common second-stage machine ［J］. Computers & operations research, 1997, 24(12): 1169-1174．
［6］ HARIRI A M A, POTTS C N. A branch and bound algorithm for the two-stage assembly scheduling problem ［J］. European Journal of Operational Research, 1997, 103(3): 547556．
［7］ 赵月, 胡玉梅. 求解可重入并行机调度的混台禁忌搜索算法［J］.计算机应用, 2012, 32(9): 2451-2454．
ZHAO Yue, HU Yu-mei. Hybrid tabu search for scheduling reentrant jobs on parallel machines ［J］. Journal of Computer Applications, 2012, 32(9): 2451-2454．
［8］ 张洁, 张朋, 刘国宝. 基于两阶段蚁群算法的带非等效并行机的作业车间调度［J］. 机械工程学报, 2013, 49(6): 136-144．
ZHANG Jie, ZHANG Peng, LIU Guo-bao. Two-stage ant colony algorithm based job shop scheduling with unrelated parallel machines ［J］. Journal of Mechanical Engineering, 2013, 49(6): 136-144．
［9］ 陈亮, 王世进, 周炳海. 柔性作业车间调度问题的集成启发式算法［J］. 计算机工程, 2008, 34(1): 256-258．
CHEN Liang, WANG Shi-jin, ZHOU Bing-hai. Integrated heuristic algorithm for flexible job-shop scheduling problems ［J］. Computer Engineering, 2008, 34(1): 256-258．
［10］ 庄新村, 卢宇灏, 李从心. 基于遗传算法的车间调度问题［J］. 计算机工程, 2006, 32(1): 193-194．
ZHUANG Xin-cun, LU Yu-hao, LI Cong-xin. Solving job shop scheduling problem by genetic algorithm ［J］. Computer Engineering, 2006, 32(1): 193-194．
［11］ ZHENG D Z, WANG L. An effective hybrid heuristic for flow shop scheduling ［J］. The International Journal of Advanced Manufacturing Technology, 2003, 21(1): 38-44．
[1] 朱东阳, 沈静逸, 黄炜平, 梁军. 基于主动学习和加权支持向量机的工业故障识别[J]. 浙江大学学报(工学版), 2017, 51(4): 697-705.
[2] 丰小月, 梁艳春, 林希珣, 管仁初. 永恒语言学习研究与发展[J]. 浙江大学学报(工学版), 2017, 51(1): 82-88.
[3] 裘日辉, 刘康玲, 谭海龙, 梁军. 基于极限学习机的分类算法及在故障识别中的应用[J]. 浙江大学学报(工学版), 2016, 50(10): 1965-1972.
[4] 冀瑜,邱清盈,冯培恩,黄浩. 国际专利分类表中设计知识的提取和利用[J]. 浙江大学学报(工学版), 2016, 50(3): 412-418.
[5] 居斌, 钱沄涛, 叶敏超. 基于结构投影非负矩阵分解的协同过滤算法[J]. 浙江大学学报(工学版), 2015, 49(7): 1319-1325.
[6] 王国芳, 方舟, 李平. 基于批量递归最小二乘的自然Actor-Critic算法[J]. 浙江大学学报(工学版), 2015, 49(7): 1335-1342.
[7] 谭海龙, 刘康玲, 金鑫, 石向荣, 梁军. 基于μσ-DWC特征和树结构M-SVM的多维时间序列分类[J]. 浙江大学学报(工学版), 2015, 49(6): 1061-1069.
[8] 王立军,黄忠朝,赵于前. 基于超像素分割的空间相关主题模型及场景分类方法[J]. 浙江大学学报(工学版), 2015, 49(3): 402-408.
[9] 王成龙,李诚,冯毅萍,荣冈. 作业车间调度规则的挖掘方法研究[J]. 浙江大学学报(工学版), 2015, 49(3): 421-429.
[10] 於俊,汪增福. 基于经验模式分解和多种评价准则的电子稳像[J]. J4, 2014, 48(3): 423-429.
[11] 刘业峰，徐冠群，潘全科，柴天佑. 磁性材料成型烧结生产调度优化方法及应用[J]. J4, 2013, 47(9): 1517-1523.
[12] 林亦宁, 韦巍, 戴渊明. 半监督Hough Forest跟踪算法[J]. J4, 2013, 47(6): 977-983.
[13] 郝钏钏, 方舟, 李平. 基于参考模型的输出反馈强化学习控制[J]. J4, 2013, 47(3): 409-414.
[14] 汪鹏君, 王振海, 陈耀武, 李辉. 固定极性Reed-Muller电路最佳延时极性搜索[J]. J4, 2013, 47(2): 361-366.
[15] 李侃,黄文雄,黄忠华. 基于支持向量机的多传感器探测目标分类方法[J]. J4, 2013, 47(1): 15-22.