面向Jobshop调度的时间映射算法

工业工程 ›› 2014, Vol. 17 ›› Issue (4): 35-41.

面向Jobshop调度的时间映射算法

(大连理工大学管理与经济学部,辽宁大连 116023)

出版日期:2014-08-30 发布日期:2014-10-17
作者简介:黄学文(1968-)，男,湖北省人，副教授，博士，主要研究方向为企业管理、ERP/MES、计算机技术.
基金资助:
国家自然科学基金资助项目(70772086)；国家科技支撑计划资助项目(2013BAF02B03)

Time Mapping Algorithm for Jobshop Scheduling

(Faculty of Management and Economics, Dalian University of Technology, Dalian 116023, China)

Online:2014-08-30 Published:2014-10-17

摘要/Abstract

摘要： 现实的Jobshop生产环境中的生产日历和班次等把设备资源的有效工作时间段分割成离散状态。为了降低调度在确定工序开始和结束时间时的计算复杂性，提出了一种时间映射算法。通过该算法实现了离散作业时间到整数连续区间和整数连续区间到离散作业时间的快速转换；并以遗传调度算法为例，研究了时间映射算法与调度算法的融合技术，实现了在连续整数区间上的调度。研究结果表明，相比未采用时间映射算法的调度算法，采用时间映射算法能大幅降低调度在确定工序开始和结束时间上的计算复杂性，计算时间降幅达到39.7%，从而提高了调度的计算效率。

关键词: Jobshop调度, 时间映射算法, 生产日历

Abstract: The work calendar and shift in realistic jobshop production environment split the effective work time of machine into a discrete state. In order to reduce the computational complexity of allocating the start and end time of a process, a time mapping algorithm (TMA) is proposed. The quick switch from discrete time spans to integral continuous intervals and from integral continuous intervals to discrete time spans is realized by the algorithm. Taking genetic algorithm (GA) scheduling as an example, the technology of how to integrate this algorithm with scheduling algorithms is also analyzed. The analysis illustrates that, compared with the scheduling algorithm without TMA, TMA can dramatically reduce the computational complexity of scheduling on allocating the start and end time of a process. By the algorithm, calculation time is reduced by 39.7% and the efficiency of scheduling is improved.

Key words: Jobshop scheduling, time mapping algorithm, work calendar

黄学文，史青涛，赵兴野. 面向Jobshop调度的时间映射算法[J]. 工业工程, 2014, 17(4): 35-41.

Huang Xue-wen, Shi Qing-tao, Zhao Xing-ye. Time Mapping Algorithm for Jobshop Scheduling[J]. Industrial Engineering Journal , 2014, 17(4): 35-41.

参考文献

［1］Ow P S, Smith S F. Viewing scheduling as an opportunistic problemsolving process［J］. Annals of Operation Research, 1988, 12(1): 85-108. ［2］Naderi B, Khalili M, TavakkoliMoghaddam R. A hybrid artificial immune algorithm for a realistic variant of job shops to minimize the total completion time［J］. Computers & Industrial Engineering, 2009, 56(4): 1494-1501. ［3］Lock D. The essentials of project management［M］. Gower: Gower Publishing, Ltd., 2007. ［4］AlvarezValdes R, Fuertes A, Tamarit J M, et al. A heuristic to schedule flexible jobshop in a glass factory［J］. European Journal of Operational Research, 2005, 165(2): 525-534. ［5］Vancza J, Kis T, Kovacs A. Aggregationthe key to integrating production planning and scheduling［J］.CIRP AnnalsManufacturing Technology,2004,53(1):377-380. ［6］Lu M, Lam H C. Critical path scheduling under resource calendar constraints［J］. Journal of Construction Engineering and Management, 2008, 134(1): 25-31. ［7］Candido M A B. A genetic algorithm based procedure for more realistic job shop scheduling problems［J］. International Journal of Production Research, 1998, 36(12): 3437-3457. ［8］Chua T J, Liu M W, Wang F Y, et al. An intelligent multiconstraint finite capacitybased lot release system for semiconductor backend assembly environment［J］. Robotics and ComputerIntegrated Manufacturing, 2007, 23(3): 326-338. ［9］Slotnick S A, Morton T E. Order acceptance with weighted tardiness［J］. Computers & Operations Research, 2007, 34(10): 3029-3042. ［10］Garcia B L, Potvin B Y,Rousseau J M. A parallel implementation of tuba search heuristic for vehicle routing problem with time window constrains［J］. Computers & Operations Research, 1994, 21(9): 1025-1033. ［11］Chatfield D C. The economic lot scheduling problem: A pure genetic search approach［J］. Computers & Operations Research, 2007, 34(10): 2865-2881. ［12］Kirkpatrick S. Optimization by simulated annealing: Quantitative studies［J］. Journal of Statistical Physics, 1984, 34(5/6): 975-986 ［13］宋小宇, 朱云龙, 伊朝万,等. 应用混合蚁群算法求解模糊作业车间调度问题［J］. 计算机集成制造系统, 2007, 13(1): 105-110. Song X Y, Zhu Y L, Yi C W, et al. Hybrid ant colony algorithm for fuzzy job shop scheduling［J］. Computer Integrated Manufacturing Systems, 2007, 13(1): 105-110. ［14］Li X, Liu L, Wu C. A fast method for heuristics in largescale flow shop scheduling［J］. Tsinghua Science & Technology, 2006, 11(1): 12-18. ［15］杨晓梅, 曾建潮. 采用多个体交叉的遗传算法求解作业车间问题［J］. 计算机集成制造系统, 2004,10(9): 1114-1119. Yang X M, Zeng J C. Multiindividualcrossover genetic algorithm for job shop scheduling problem［J］. Computer Integrated Manufacturing Systems, 2004, 10(9): 11141119. ［16］Battersby A. Network analysis for planning and scheduling［M］. Basingstoke: Macmillan, 1964. ［17］Sears S K, Sears G A, Clough R H. Construction project management: a practical guide to field construction management［M］. NewYork: John Wiley & Sons, 2010. ［18］Knutson J. Project management for business professionals: a comprehensive guide［M］. NewYork : John Wiley & Sons, 2002. ［19］Kim K, de la Garza J M. Critical path method with multiple calendars［J］. Journal of Construction Engineering and Management, 2005, 131(3): 330-342. ［20］Francis A, Miresco E. Discussion of “Critical path method with multiple calendars” by Kyunghwan Kim and Jesús M. de la Garza［J］. Journal of Construction Engineering and Management, 2006, 132(5): 542-543. ［21］Jesús M, Kim K. Application of the resourceconstrained critical path method to multiple calendars and progressed schedules［M］∥Samuta TA, Eddy M R. The american society of civil engineers.USA:Constrution Research Congress,2009: 916-925. ［22］Lu M, Lam H C, Dai F. Resourceconstrained critical path analysis based on discrete event simulation and particle swarm optimization［J］. Automation in Construction, 2008, 17(6): 670-681. ［23］Taillard E. Benchmarks for basic scheduling problems［J］. European Journal of Operational Research, 1993, 64(2): 278-285.