考虑多约束的MOJ调度问题

doi:10.3969/j.issn.1005-3026.2015.10.030

东北大学学报:自然科学版 ›› 2015, Vol. 36 ›› Issue (10): 1506-1511.DOI: 10.3969/j.issn.1005-3026.2015.10.030

考虑多约束的MOJ调度问题

周炳海，王腾，方腾

(同济大学机械与能源工程学院，上海201804)

收稿日期:2014-03-12 修回日期:2014-03-12 出版日期:2015-10-15 发布日期:2015-09-29
通讯作者: 周炳海
作者简介:周炳海(1965- )，男，浙江浦江人，同济大学教授，博士生导师.
基金资助:
国家自然科学基金资助项目(71471135， 61273035).

Scheduling Multiple Orders per Job with Various Constraints

ZHOU Bing-hai， WANG Teng， FANG Teng

School of Mechanical Engineering， Tongji University， Shanghai 201804， China.

Received:2014-03-12 Revised:2014-03-12 Online:2015-10-15 Published:2015-09-29
Contact: ZHOU Bing-hai
About author:-
Supported by:
-

摘要/Abstract

摘要： 统筹考虑晶圆加工过程中的多品种、p-s-d(past-sequence-dependent)换模时间及衰退效应等约束特征，以总加权提前/拖期惩罚成本最小为优化目标，建立了单机MOJ(multiple orders per job)调度数学规划模型.在此基础上，对决策变量进行分离，提出具有双层嵌套编码机制的改进型遗传蚁群调度算法.该算法将遗传算法融合到动态自适应蚁群算法的每一次迭代过程中，并为有效提高算法的收敛性能，引入ATCS(apparent tardiness cost with setups)修正准则.最后，仿真实验结果表明，该算法是有效、可行的.

关键词: 多品种, p-s-d换模时间, 衰退效应, 调度, 改进型遗传蚁群算法

Abstract: Taking a comprehensive consideration of the characteristics of multiple product types， the past-sequence-dependent (p-s-d) setup time and the deterioration effects constraints in processes of wafer fabrication， with an objective function of minimizing total weighted earliness-tardiness penalties cost， a mathematical programming model of scheduling multiple orders per job (MOJ) in a single machine was built. On this basis， the decision-making variables were separated， and a modified genetic algorithm-ant colony optimization (MGA-ACO) algorithm adopting two-level encoding mechanism was put forward. Genetic algorithm was converged to the process of dynamic and adaptive ant colony iterations. To improve the algorithm convergence performance， a modified rule of apparent tardiness cost with setups (ATCS) was applied. Finally， the simulation results indicated that the developed algorithm is valid and feasible.

Key words: multiple product types, p-s-d setup time, deterioration effects, scheduling, MGA-ACO algorithm

中图分类号:

TP391

周炳海，王腾，方腾. 考虑多约束的MOJ调度问题[J]. 东北大学学报:自然科学版, 2015, 36(10): 1506-1511.

ZHOU Bing-hai， WANG Teng， FANG Teng. Scheduling Multiple Orders per Job with Various Constraints[J]. Journal of Northeastern University:Natural Science, 2015, 36(10): 1506-1511.

参考文献

[1]Qu P，Mason S J.Using tabu search on the single machine multi-orders per job scheduling problem ［C］//IIE Annual Conference and Exhibition. Houston:Institute of Industrial Engineers，2004:1831-1835.
[2]Sobeyko O，Monch L.Genetic algorithms to solve a single machine multiple orders per job scheduling problem ［C］//2010 Winter Simulation Conference. Piscataway:IEEE，2010:2493 – 2503.
[3]Jampani J，Mason S J.Column generation heuristics for multiple machine，multiple orders per job scheduling problems［J］.Annals of Operations Research，2008，159(1):261-273.
[4]Mason S J，Chen J S.Scheduling multiple orders per job in a single machine to minimize total completion time［J］. European Journal of Operational Research，2010，207(1):70-77.
[5]Erramilli V，Mason S J.Multiple orders per job compatible batch scheduling［J］.IEEE Transactions on Electronics Packaging Manufacturing，2006，29 (4):285-296.
[6]Erramilli V，Mason S J.Multiple orders per job batch scheduling with incompatible jobs［J］.Annals of Operations Research，2008，159(1):245-260.
[7]Chen J S.Optimization models for the flow-shop scheduling problem with multiple orders per job［C］//The 40th International Conference on Computers and Industrial Engineering.Piscataway:IEEE，2010:1-6.
[8]Zhou B H，Zhai Z Q.Lifetime distribution model of port facilities with pitting corrosion of stochastic processes［J］.Applied Mechanics and Materials，2011，44:46-50.
[9]Shen L X，Wu Y B.Single machine past-sequence-dependent delivery times scheduling with general position-dependent and time-dependent learning effects［J］. Applied Mathematical Modelling，2013，37(7):5444-5451.
[10]Qu P，Mason S J.Metaheuristic scheduling of 300 mm jobs containing multiple orders［J］. IEEE Transactions on Semiconductor Manufacturing，2005，18(4):633-643.
[11]Pfund M，Fowler J W，Gadkari A，et al.Scheduling jobs on parallel machines with setup times and ready times［J］. Computers & Industrial Engineering，2008，54(4):764-782.

[1]	耿蓉，张昭，牛天水，王宇飞. 基于改进蚁群算法的天基资源调度研究与仿真[J]. 东北大学学报（自然科学版）, 2023, 44(2): 168-176.
[2]	房晓晴，刘书含，孙文强. 高炉煤气管网水力建模及调度策略[J]. 东北大学学报（自然科学版）, 2023, 44(1): 69-75.
[3]	丁山，臧仕义，曹殿明，佘黎煌. 基于动态ID跳变的CAN总线安全调度算法[J]. 东北大学学报（自然科学版）, 2022, 43(3): 350-358.
[4]	孙磊，陈彦峰，常爽爽，邓庆绪. 电动汽车弹性充电策略的研究[J]. 东北大学学报（自然科学版）, 2022, 43(10): 1383-1390.
[5]	杜子超，卢福强，王素欣，王雷震. 众包物流配送车辆调度模型及优化[J]. 东北大学学报（自然科学版）, 2021, 42(8): 1210-1216.
[6]	姜旭艳，严锦立，全巍，孙志刚. SSA:一种面向CQF模型的TSN资源调度算法[J]. 东北大学学报:自然科学版, 2020, 41(6): 784-791.
[7]	王生生，张伟，董如意，李文辉. 改进蚱蜢算法在电动汽车充换电站调度中的应用[J]. 东北大学学报:自然科学版, 2020, 41(2): 170-175.
[8]	李稷，徐安军. 炼钢车间多天车动态调度仿真方案[J]. 东北大学学报:自然科学版, 2020, 41(12): 1699-1707.
[9]	周炳海，顾佳颖. 考虑多资源约束的非等效并行机节能调度算法[J]. 东北大学学报:自然科学版, 2019, 40(3): 403-408.
[10]	韩美灵，邓庆绪，张天宇，林宇晗. 基于G-EDF的DAG并行任务多核响应时间分析[J]. 东北大学学报:自然科学版, 2019, 40(3): 315-320.
[11]	周炳海，谭芬. 基于循环配送策略的汽车装配线物料配送调度方法[J]. 东北大学学报:自然科学版, 2018, 39(3): 389-393.
[12]	王生生，杜鹏，董如意，李永贺. 改进的花朵授粉算法在微网优化调度中的应用[J]. 东北大学学报:自然科学版, 2018, 39(3): 334-338.
[13]	曾程宽，刘士新. 缓冲区间有限条件下的作业车间调度方法[J]. 东北大学学报:自然科学版, 2018, 39(12): 1679-1684.
[14]	王旭，刘士新，王佳. 求解具有时空约束的板坯库天车调度问题Memetic算法[J]. 东北大学学报:自然科学版, 2017, 38(7): 913-917.
[15]	陈迪，孙福权，刘士新. MRO服务中心多技能员工优化调度模型[J]. 东北大学学报:自然科学版, 2016, 37(7): 927-930.

考虑多约束的MOJ调度问题

Scheduling Multiple Orders per Job with Various Constraints

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价