Shortest time interval based algorithm for on-line job scheduling
GAO Li-qing1, WANG Yan-zhang1, XU Xi-rong2
1. Institute of Information and Decision Technology, Dalian University of Technology, Dalian 116023, China; 2. School of Computer Science and Technology, Dalian University of Technology, Dalian 116023, China
Abstract：In this paper, we are mainly concerned with the on-line job scheduling problem in the order-oriented enterprise. By analyzing time intervals on devices that a new task can be inserted in, an algorithm based on shortest time interval for on-line job scheduling is proposed. Its main idea is to model the scheduling problem as an acyclic digraph in graph theory, and then the scheduling can be realized by adding vertices and edges in a digraph. Simulation results show that the algorithm performs well with guaranteeing the deadline of each other, and changes little the relative execution sequences of tasks on each device. There are fewer time intervals on devices when orders come frequently, and the utilization rate of devices is very high, reaching nearly 94% in the simulation results. In addition, the algorithm runs fast. Thus, it is suitable for solving large-scale on-line job scheduling problem.
[1] Garey M R, Johnson D S, Sethi R. The complexity of flowshop and jobshop scheduling[J]. Mathematics of Operations Research, 1976, 1(2): 117-129. [2] Bruker P, Schlie R. Job-shop scheduling with multi-purpose machines[J]. Computing, 1990, 45(4): 369-375. [3] Nowicki E, Smutnicki C. A fast taboo search algorithm for the job shop problem[J]. Management Science, 1996, 42(6): 797-813. [4] Nowicki E, Smutnicki C. An advanced tabu search algorithm for the job shop problem[J]. Journal of Scheduling, 2005, 8(2): 145-159. [5] Saidi-Mehrabad M, Fattahi P. Flexible job shop scheduling with tabu search algorithms[J]. The International Journal of Advanced Manufacturing Technology, 2007, 32(5-6): 563-570. [6] Peng B, Lü Z, Cheng T C E. A tabu search path relinking algorithm to solve the job shop scheduling problem[J]. Computers & Operations Research, 2015, 53: 154-164. [7] Pezzella F, Morganti G, Ciaschetti G. A genetic algorithm for the flexible job-shop scheduling problem[J]. Computers & Operations Research, 2008, 35(10): 3202-3212. [8] 王万良, 吴启迪, 宋毅. 求解作业车间调度问题的改进自适应遗传算法[J]. 系统工程理论与实践, 2004, 24(2): 58-62. Wang Wanliang, Wu Qidi, Song Yi. Modified adaptive genetic algorithms for solving job shop scheduling problems[J]. Systems Engineering——Theory & Practice, 2004, 24(2): 58-62. [9] 袁坤,朱剑英. 一种求解多目标柔性Job Shop 调度的改进遗传算法[J].中国机械工程, 2007, 18(2): 156-160.Yuan Kun, Zhu Jianying. Improved genetic algorithm for the flexible job-shop scheduling with multi-object[J]. China Mechanical Engineering, 2007, 18(2): 156-160. [10] 李琳, 霍佳震. 钢管生产计划中的多目标柔性 Job-shop 调度问题[J]. 系统工程理论与实践, 2009, 29(8): 117-126. Li Lin, Huo Jiazhen. Multi-objective flexible Job-shop scheduling problem in steel tubes production[J]. Systems Engineering——Theory & Practice, 2009, 29(8): 117-126. [11] 李琳, 霍佳震. 带有限容量缓冲库的多目标柔性作业车间调度优化[J]. 系统工程理论与实践, 2010, 30(10): 1803-1814. Li Lin, Huo Jiazhen. Multi-objective flexible job shop scheduling with buffer storage constraints[J]. Systems Engineering——Theory & Practice, 2010, 30(10): 1803-1814. [12] 宋莉波,徐学军,孙延明,等.一种求解柔性工作车间调度问题的混合遗传算法[J].管理科学学报, 2010, 13(11): 49-54.Song Libo, Xu Xuejun, Sun Yanming, et al. A hybrid genetic algorithm for flexible job shop scheduling problem[J]. Journal of Management Sciences in China, 2010, 13(11): 49-54. [13] 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. [14] 刘志勇,吕文阁,谢庆华,等．应用改进蚁群算法求解柔性作业车间调度问题[J].工业工程与管理, 2010, 15(3): 115-119.Liu Zhiyong, Lü Wenge, Xie Qinghua, et al. Solving flexible job-shop scheduling problem based on an improved ant colony optimization algorithm[J]. Industrial Engineering and Management, 2010, 15(3): 115-119. [15] Xing L N, Chen Y W, Wang P, et al. A knowledge-based ant colony optimization for flexible job shop scheduling problems[J]. Applied Soft Computing, 2010, 10(3): 888-896. [16] 张其亮,陈永生. 基于混合粒子群-NEH算法求解无等待柔性流水车间调度问题[J].系统工程理论与实践, 2014, 34(3): 802-809.Zhang Qiliang, Chen Yongsheng. Hybrid PSO-NEH algorithm for solving no-wait flexible flow shop scheduling problem[J]. Systems Engineering——Theory & Practice, 2014, 34(3): 802-809. [17] 何小娟,曾建潮. 基于Bayesian统计推理的分布估计算法求解柔性作业车间调度问题[J].系统工程理论与实践, 2012, 32(2): 380-388.He Xiaojuan, Zeng Jianchao. Solving flexible job-shop scheduling problems with Bayesian statistical inference-based estimation of distribution algorithm[J]. Systems Engineering——Theory & Practice, 2012, 32(2): 380-388. [18] 苏国军,汪晋,田立国. 基于Petri网模型的柔性制造系统优化调度[J].系统工程理论与实践, 2014, 34(10): 2716-2721.Su Guojun, Wang Jin, Tian Liguo. The FMS optimal scheduling based on Petri net model[J]. Systems Engineering——Theory & Practice, 2014, 34(10): 2716-2721. [19] Pruhs K, Sgall J, Torng E. Online scheduling[M]//Handbook of Scheduling: Algorithms, models, and performance analysis. 2004. [20] Fu R, Cheng T C E, Ng C T, et al. An optimal online algorithm for single parallel-batch machine scheduling with incompatible job families to minimize makespan[J]. Operations Research Letters, 2013, 41(3): 216-219. [21] Batsyn M, Goldengorin B, Pardalos P M, et al. Online heuristic for the preemptive single machine scheduling problem of minimizing the total weighted completion time[J]. Optimization Methods and Software, 2014, 29(5): 955-963. [22] Li W, Gao J, Yuan J. Online-list scheduling on a single bounded parallel-batch machine to minimize makespan[J]. Asia-Pacific Journal of Operational Research, 2015: 1550028. [23] Li W. A best possible online algorithm for the parallel-machine scheduling to minimize the maximum weighted completion time[J]. Asia-Pacific Journal of Operational Research, 2015: 1550030. [24] Proth J M. Scheduling: New trends in industrial environment[J]. Annual reviews in control, 2007, 31(1): 157-166.
2015, Vol. 35 
