Genetic Evalution Method for JSP under Mixed Work Calendars

Abstract

Abstract: A genetic evolution method was presented to solve a kind of JSP under mixed work calendars. Firstly，a job shop scheduling optimization model was established under mixed work calendars to minimize production cycle. Secondly，a time reckoning method was proposed based on work calendar,and a GA was designed to solve the problems above. The process-based encoding method was used to encode chromosomes. An improved strategy of genetic operators was used in genetic operations to ensure feasibility of chromosomes and reduce calculation amounts. In decoding operation，the proposed time reckoning method was used to calculate start time and end time of each operation accurately based on the work calendar，and two techniques were adopted to shorten production cycle.Finally，application results show that the proposed method may solve the JSP under mixed work calendars effectively.

Key words: job shop scheduling problem(JSP), mixed work calendar, genetic algorithm(GA), time reckoning

摘要： 针对一类混合工作日历下的作业车间调度问题，提出了一种遗传进化方法。构建了混合工作日历下以生产周期最短为优化目标的作业车间调度优化模型；提出了基于工作日历的时间推算方法，设计了遗传算法对这类问题进行求解。算法采用基于工序的编码方式；遗传操作中采用遗传算子改进策略保证子代个体的可行性，降低了计算量；解码操作中采用了基于工作日历的时间推算方法来准确计算工序的起止时刻，并采用两种技术缩短生产周期。通过案例分析验证了所提方法的有效性。

关键词: 作业车间调度问题, 混合工作日历, 遗传算法, 时间推算

CLC Number:

C93-03
TP391

ZENG Qiang, DENG Jingyuan, CHANG Menghui, ZHANG Jinchun. Genetic Evalution Method for JSP under Mixed Work Calendars[J]. China Mechanical Engineering.

曾强, 邓敬源, 常梦辉, 张进春. [车间调度]混合工作日历下作业车间调度遗传进化方法[J]. 中国机械工程.

References

[1]LENSTRA J K，RINNOOY KAN A H G，BRUCKER P. Complexity of Machine Scheduling Problems[J]. Annals of Discrete Mathematics，1977，1: 343-362.
[2]LI J Y，HUANG Y，NIU X W. A Branch Population Genetic Algorithm for Dual-resource Constrained Job Shop Scheduling Problem[J]. Computers & Industrial Engineering，2016，102:113-131.
[3]GAO L，PAN Q K. A Shuffled Multi-swarm Micro-migrating Birds Optimizer for a Multi-resource-Constrained Flexible Job Shop Scheduling Problem[J]. Information Sciences，2016，372: 655-676.
[4]KUNDAKCI N，KULAK O. Hybrid Genetic Algorithms for Minimizing Makespan in Dynamic Job Shop Scheduling Problem[J]. Computers & Industrial Engineering，2016，96: 31-51.
[5]BEKKAR A，GUEMRI O，BEKRAR A，et al. An Iterative Greedy Insertion Technique for Flexible Job Shop Scheduling Problem[J]. IFAC-Papers on Line，2016，49(12): 1956-1961.
[6]熊唯，李宗斌，郝建波. 解决动态作业车间调度关键问题的方法研究[J]. 组合机床与自动化加工技术，2008，(7): 105-108.
XIONG Wei，LI Zongbin，HAO Jianbo. Research on Solving the Key Problem of Dynamic Job Shop Scheduling[J]. Modular Machine Tool & Automatic Manufacturing Technique，2008，(7): 105-108.
[7]万春辉，闫艳，武志军，等. 面向车间生产动态调度的动态工作日制研究[J]. 组合机床与自动化加工技术，2006(3): 102-104.
WAN Chunhui，YAN Yan，WU Zhijun et al. Research and Realization of Dynamic Shop Calendar Orienting Dynamic Scheduling[J]. Modular Machine Tool & Automatic Manufacturing Technique，2006(3): 102-104.
[8]钱晓龙，唐立新，刘文新. 动态调度的研究方法综述[J]. 控制与决策，2001，16(2): 141-145.
QIAN Xiaolong，TANG Lixin，LIU Wenxin. Dynamic Scheduling:a Survey of Research Methods[J]，Control and Decision，2001，16(2): 141-145.
[9]范华丽，熊禾根，蒋国璋，等. 动态车间作业调度问题中调度规则算法研究综述[J]. 计算机应用研究，2016，33(3): 648-653.
FAN Huali，XIONG Hegen，JIANG Guozhang et al. Survey of Dispatching Rules for Dynamic Job-shop Scheduling Problem[J]. Application Research of Computers，2016，33(3): 648-653.
[10]ZHANG G H，GAO L，SHI Y. An Effective Genetic Algorithm for the Flexible Job-shop Scheduling Problem[J]. Expert Systems with Applications，2011，38: 3563-3573.
[11]ASADZADEH L. A Local Search Genetic Algorithm for the Job Shop Scheduling Problem with Intelligent Agents[J]. Computers & Industrial Engineering，2015，85: 376-383.
[12]ZHANG C Y，LI P G，GUAN Z L，et al. A Tabu Search Algorithm with a New Neighborhood Structure for the Job Shop Scheduling Problem[J]. Computers & Operations Research，2007，34(11): 3229-3242.
[13]KOLONKO M. Some New Results on Simulated Annealing Applied to the Job Shop Scheduling Problem[J]. European Journal of Operational Research，1999，113(1): 123-136.
[14]MOHAMMAD S M，SAEED D A，FARSHID E，et al. An Ant Colony Algorithm(ACA) for Solving the New Integrated Model of Job Shop Scheduling and Conflict-free Routing of AGVs[J]. Computers & Industrial Engineering，2015，86: 2-13.
[15]ZHAO F Q，TANG J X，WANG J B，et al. An Improved Particle Swarm Optimization with Decline Disturbance Index(DDPSO) for Multi-objective Job-shop Scheduling Problem[J]. Computers & Operations Research，2014，45: 38-50.
[16]GAO K Z，SUGANTHAN P N，PAN Q K，et al. Artificial Bee Colony Algorithm for Scheduling and Rescheduling Fuzzy Flexible Job Shop Problem with New Job Insertion[J]. Knowledge-Based Systems，2016，109: 1-16.
[17]CHAKRI A，KHELIF R，BENOUARET M，et al. New Directional Bat Algorithm for Continuous Optimization Problems[J]. Expert Systems with Applications，2017，69: 159-175.
[18]SIMPSON D. Job Shop Scheduling Problem with a Novel Particle Swarm Optimization Based on Tabu Search[C]// 2009 International Conference on Artificial Intelligence and Computational Intelligence. Shanghai，2009: 97-100.
[19]LI X Y，GAO L. An Effective Hybrid Genetic Algorithm and Tabu Search for Flexible Job Shop Scheduling Problem[J]. International Journal of Production Economics，2016，174: 93-110.
[20]陈华平，谷峰，卢冰原，等. 自适应多目标遗传算法在柔性工作车间调度中的应用[J]. 系统仿真学报，2006，18(8): 2271-2274.
CHEN Huaping，GU Feng，LU Bingyuan，et al. Application of Self-adaptive Multi-objective Genetic Algorithm in Flexible Job Shop Scheduling[J]. Journal of System Simulation，2006，18(8): 2271-2274.
[21]周亚勤，李蓓智，杨建国. 考虑批量和辅助时间等生产工况的智能调度方法[J]. 机械工程学报，2006，42(1): 52-56.
ZHOU Yaqin，LI Beizhi，YANG Jianguo.Intelligent Scheduling Algorithm for Problems with Batch and Non Cutting Time[J]. Chinese Journal of Mechanical Engineering，2006，42(1): 52-56.
[22]潘全科，朱剑英. 多工艺路线多资源多目标的作业调度优化[J]. 中国机械工程，2005，16(20): 1821-1826.
PAN Quanke，ZHU Jianying. An Optimization Method for a Multi-objective Job-shop Scheduling Problem under Multi-resource Constraints[J]. China Mechanical Engineering，2005，16(20): 1821-1826.