一类带有deadline约束的作业车间提前/拖期调度问题研究

中国机械工程 ›› 2012, Vol. 23 ›› Issue (15): 1811-1818.

一类带有deadline约束的作业车间提前/拖期调度问题研究

李海宁;孙树栋

西北工业大学,西安,710072

出版日期:2012-08-10 发布日期:2012-09-05
基金资助:
国家自然科学基金资助项目(51075337)
National Natural Science Foundation of China（No. 51075337）

Genetic Algorithm for Job Shop Earliness and Tardiness Scheduling Problems with Deadlines

Li Haining;Sun Shudong

Northwestern Polytechnical University,Xi'an,710072

Online:2012-08-10 Published:2012-09-05
Supported by:
National Natural Science Foundation of China（No. 51075337）

摘要/Abstract

摘要：

针对带有零件deadline时间约束的一类作业车间提前/拖期调度问题,设计了一种改进型遗传算法(EGA)。EGA算法采用拖期优先的调度策略,将原有的非正规性能指标的E/T调度问题转化为拖期子问题、修复子问题和提前子问题,以此来降低E/T调度问题的求解复杂度。采用基于工序的编码方法,在染色体解码过程中,分别采用了主动解码、染色体修复和逆向重调度三阶段的解码操作,以期实现在满足零件deadline约束的前提下尽可能降低提前/拖期惩罚总成本。180个调度测试用例仿真结果表明,EGA算法在解决问题数、寻优能力、调度结果的均衡性等方面具有一定的优势。

关键词: 作业车间调度, 提前/拖期, deadline约束, 遗传算法, 染色体解码

Abstract:

This paper studied a job shop scheduling problem with due dates and deadlines in the presence of tardiness and earliness penalties.In order to solve this problem,an enhanced genetic algorithm(EGA) was introduced herein.EGA utilized an operation-based scheme to represent schedules as chromosomes.After the initial population of chromosomes was randomly generated,each chromosome was processed through a three-stage decoder,to reduce the total earliness and tardiness penalties with meeting deadline constraint of jobs, in which the active decoding, chromosome repair and reverse rescheduling was operated in turn.The proposed algorithm was tested on 180 job shop scheduling problems of varying sizes and its performance was discussed.

Key words: Job shop scheduling, earliness and tardiness, deadline constraint, genetic algorithm, chromosome decoding

中图分类号:

TP301

李海宁, 孙树栋. 一类带有deadline约束的作业车间提前/拖期调度问题研究[J]. 中国机械工程, 2012, 23(15): 1811-1818.

LI Hai-Ning, SUN Shu-Dong. Genetic Algorithm for Job Shop Earliness and Tardiness Scheduling Problems with Deadlines[J]. China Mechanical Engineering, 2012, 23(15): 1811-1818.

参考文献

[1]Lauff V, Werner F. Scheduling with Common Due Date,Earliness and Tardiness Penalties for Multimachine Problems: A Survey[J]. Mathematical and Computer Modelling, 2004,40(5/6) : 637-655.
[2]Sen T,Sulek J M,Dileepan P. Static Scheduling Re search to Minimize Weighted and Unweighted Tar diness: A State- of- the- art Survey[J]. Int. J. Production Economics,2003,83(1) : 1-12.
[3]Essafi I, Mati Y, Stephane D P. A Genetic Local Search Algorithm for Minimizing Total Weighted Tardiness in the Job-shop Scheduling Problem [J]. Computers & Operations Research, 2008, 35 (8): 2599-2616.
[4]Thiagarajan S, Rajendran C. Scheduling in Dynamic Assembly Job-shops to Minimize the Sum of Weighted Earliness, Weighted Tardiness and Weighted Flowtime of Jobs[J]. Computers & Industrial Engineering, 2005,49 (4): 463-503.
[5]姚伟力,杨德礼.Job—shop提前／拖期调度问题的研究[J].控制与决策,2000,15(3):322-324.
[6]Sadeh N. Micro-boss : A Micro- opportunistic Factory Scheduler [J]. Expert Systems with Applications,1993,6(3) :377-392.
[7]刘兴初,赵千川.用GA算法解不同交货期窗口下的E／T调度问题[J].清华大学学报：自然科学版,2000,40(7):59-62.
[8]黄德才[1],朱艺华[2],王万良[1].带公共交货期窗口的提前／拖期非等同多机调度问题[J].系统工程理论与实践,2001,21(4):64-69.
[9]王凌.车间调度及其遗传算法[M],2003.
[10]张超勇[1],饶运清[1],刘向军[1],李培根[1].基于POX交叉的遗传算法求解Job—Shop调度问题[J].中国机械工程,2004,15(23):2149-2153.
[11]Baker K R. Introduction to Sequencing and Scheduling[M]. New York : Wisely, 1974.
[12]Beck J C,Refalo P. A Hybrid Approach to Scheduling with Earliness and Tardiness Costs[J]. Annals of Operations Research,2003,118(1/4) :49-71.
[13]Taillard E. Benchmarks for Basic Scheduling Problems[J]. European Journal of Operational Research, 1993,64(2):278-285.

[1]	李西兴, 杨道明, 李鑫, 吴锐, . 基于混合遗传鲸鱼优化算法的柔性作业车间自动导引车融合调度方法[J]. 中国机械工程, 2021, 32(08): 938-950，986.
[2]	赵丽娟, 王雅东, 王斌. 含夹矸煤层条件下采煤机螺旋滚筒工作性能分析与预测[J]. 中国机械工程, 2021, 32(08): 976-986.
[3]	刘雪梅；刘涛；郭欢. 基于可用度评价的混联生产线缓冲区配置优化[J]. 中国机械工程, 2020, 31(18): 2220-2230.
[4]	岳彩旭;刘鑫;刘智博;谢娜;王彦武. 基于有限元仿真的拼接模具铣削用刀具优化[J]. 中国机械工程, 2020, 31(17): 2085-2094.
[5]	刘雪梅1;王笑1;柳跃雷2. 模糊时间窗约束下的装配线物料配送方案优化[J]. 中国机械工程, 2020, 31(17): 2095-2103.
[6]	吕佑龙;许鸿伟;郑城;张洁;郑鹏. 基于混合式特征选择模型的晶圆允收测试关键参数识别方法[J]. 中国机械工程, 2020, 31(16): 1978-1984,1997.
[7]	杨杰, 胡琦, 肖亭, 张文颖, 张超勇. 基于能耗的冷轧连退机组能效建模与工艺参数优化及排序建模优化[J]. 中国机械工程, 2020, 31(14): 1724-1732.
[8]	李益兵1,2;黄炜星1;吴锐1. 基于改进人工蜂群算法的多目标绿色柔性作业车间调度研究[J]. 中国机械工程, 2020, 31(11): 1344-1350,1385.
[9]	刘建胜;雷兆发;聂伟豪;涂海宁. 一种鱼骨仓储布局下的拣选路径优化方法[J]. 中国机械工程, 2020, 31(10): 1225-1232.
[10]	吕凤鹏;李朝阳;黄健;陈兵奎. RV减速器转臂轴承的优化设计[J]. 中国机械工程, 2020, 31(09): 1043-1048.
[11]	郭祥雨;王琳;张永健. 规则约束下基于免疫遗传算法的机加工艺规划[J]. 中国机械工程, 2020, 31(04): 482-488.
[12]	张恒;李爱平;傅翔;邵焕;刘雪梅. 面向混批加工的装夹方案选择与线平衡集成优化方法[J]. 中国机械工程, 2019, 30(20): 2497-2504.
[13]	聂黎1;张国辉2;王小刚1;白跃伟1. 基于博弈论的虚拟制造网络车间调度优化方法[J]. 中国机械工程, 2019, 30(12): 1492-1497.
[14]	盛继新1;张邦基1;朱波2;王明1;金秋谈1. 两挡纯电动汽车传动系统参数优化和试验对比[J]. 中国机械工程, 2019, 30(07): 763-770,776.
[15]	贺长征1;宋豫川1;雷琦1;吕向飞1;刘软香1;陈进2. 柔性作业车间多自动导引小车和机器的集成调度[J]. 中国机械工程, 2019, 30(04): 438-447.