An Improved Ant Colony Algorithm for Solving Single Machine Total Weighted Delay Scheduling Problem

Abstract

Abstract: A single machine scheduling problem under minimized total weighted tardiness was studied, and an improved ant colony algorithm was proposed herein based on pheromone updating differently. The algorithm used a coding method which was based on job sequence, and improved the setting of heuristic information by priority rule of modified due date. The pheromone between nodes was updated adaptively and differently by the positive and negative feedback mechanism. A pairwise exchange strategy was used for local search to further improve the quality of scheduling scheme. Finally, simulations on multiple benchmark instances in OR-Library show that the proposed algorithm is feasible and effective.

Key words: ant colony algorithm, single machine scheduling, heuristic information, local optimization.

摘要： 针对极小化总加权延迟指标下的单机调度问题研究，提出一种基于信息素差异更新的改进蚁群算法。采用基于工件序列的编码方式，并结合修正交货期优先规则改进了启发式信息的设定；引入正负反馈机制来自适应地差异化更新各节点间信息素，同时将成对交换策略用于局部搜索，以进一步改善调度方案质量。结合OR-Library中多个基准实例的仿真验证了该算法的可行性和有效性。

关键词: 蚁群算法, 单机调度, 启发式信息, 局部优化

CLC Number:

TP18

QIAO Dongping, PEI Jie, WEN Xiaoyu, XIAO Yanqiu, JIAO Jianqiang, . An Improved Ant Colony Algorithm for Solving Single Machine Total Weighted Delay Scheduling Problem[J]. China Mechanical Engineering.

乔东平, 裴杰, 文笑雨, 肖艳秋, 焦建强, . [车间调度]一种求解单机总加权延迟调度问题的改进蚁群算法[J]. 中国机械工程.

References

[1]LAWLER E L. A “Pseudopolynomial” Algorithm for Sequencing Jobs to Minimize Total Tardiness [J]. Annals of Discrete Mathematics, 1977, 1(8):331-342.
[2]潘全科, 王凌, 高亮,等. 基于差分进化与块结构邻域的作业车间调度优化[J]. 机械工程学报, 2010, 46(22): 182-188.
PAN Quanke, WANG Ling, GAO Liang，et al. Differential Evolution Algorithm Based on Blocks on Critical Path for Job Shop Scheduling Problems[J]. Journal of Mechanical Engineering, 2010, 46(22):182-188.
[3]BABU P, PERIDY L, PINSON E. A Branch and Bound Algorithm to Minimize Total Weighted Tardiness on a Single Processor[J]. Annals of Operations Research, 2004, 129(1/4):33-46.
[4]YIN A, WANG J. Mixed Dispatch Rule for Single Machine Total Weighted Tardiness Problem[J]. Journal of Applied Sciences, 2013, 13(21): 4616-4619.
[5]YAHYAOUI H, KRICHEN S, DERBEL B, et al. A Variable Neighborhood Descent for Solving the Single Machine Total Weighted Tardiness Problem[C]// International Conference on Modeling, Simulation and Applied Optimization. Hammamet, 2013:1-6.
[6]FU Q, CHUNG T P. A New Approach for Solving Single Machine Total Weighted Tardiness (SMTWT) Problem[C]//IEEE International Conference on Industrial Engineering and Engineering Management. Bali, 2016:438-441.
[7]SUPPIAH Y, SHEN K P. Minimizing Total Weighted Tardiness on Single Machine[J]. International Journal of Research in Science Engineering and Technology, 2015, 2: 12-18.
[8]UMIT B, KURTULAN M, KRA F. A Tabu Search Algorithm for the Single Machine Total Weighted Tardiness Problem[J]. European Journal of Operational Research, 2007, 176(3):1423-1435.
[9]MADUREIRA A, FALCAO D, PEREIRA I. Ant Colony System Based Approach to Single Machine Scheduling Problems: Weighted Tardiness Scheduling Problem[C]// Nature and Biologically Inspired Computing. Mexico City, 2012:86-91.
[10]叶强, 刘心报, 程浩. 改进蚁群算法求解单机总加权延迟调度问题[J]. 系统仿真学报, 2008, 20(8):2052-2055.
YE Qiang，LIU Xinbao, CHENG Hao. Improved Ant Colony Algorithm for Single Machine Total Weighted Tardiness Scheduling Problem [J]. Journal of System Simulation, 2008, 20(8):2052-2055.
[11]COLORNI A, DORIGO M, MANIEZZO V. Distributed Optimization by Ant Colonies[C]//Proceedings of the First European Conference on Artificial Life. Paris ,1991: 134-142.
[12]凌海峰, 王西山. 求解柔性作业车间调度问题的两阶段参数自适应蚁群算法[J]. 中国机械工程, 2013, 24(24):3380-3385.
LING Haifeng，WANG Xishan. A Two-stage Parameter Adaptive Ant Colony Algorithm for Flexible Job Shop Scheduling Problem[J]. China Mechanical Engineering, 2013, 24(24):3380-3385.
[13]侯仰强, 王天琪, 李亮玉,等. 基于蚁群算法-粒子群算法的白车身侧围点焊机器人路径规划[J]. 中国机械工程, 2017, 28(24):2990-2994.
HOU Yangqiang，WANG Tianqi, LI Lianyu，et al. Path Planning of Spot Welding Robots in Sides of BIW Based on ACO-PSO[J]. China Mechanical Engineering, 2017, 28(24):2990-2994.
[14]ANGHINOLFI D, PAOLUCCI M. A New Ant Colony Optimization Approach for the Single Machine Total Weighted Tardiness Scheduling Problem[J]. International Journal of Operations Research, 2008(1): 44-60.
[15]BEASLEY J E. OR-Library [DB/OL]. (2018-2-14) [2018-4-5].http://people.brunel.ac.uk/~mastjjb/jeb/info.html.
[16]段海滨. 蚁群算法原理及其应用[M]. 北京: 科学出版社, 2005.
DUAN Haibin. Ant Colony Algorithm: Theory and Applications[M]. Beijing: Science Press, 2005.
[17]SOBEYKO O, MONCH L. Genetic Algorithms to Solve a Single Machine Multiple Orders Per Job Scheduling Problem[C]// Proceedings of the 2010 Winter Simulation Conference. Piscataway, 2010:2493-2503.