An effective ant colony optimization algorithm for multi-objective job-shop scheduling with equal-size lot-splitting

作者：Huang Rong Hwa; Yu Tung Han^*

来源：Applied Soft Computing, 2017, 57: 642-656.

DOI：10.1016/j.asoc.2017.04.062

• Ant colony optimization
• Job shop
• Lot-splitting
• Mathematical programming
• Multi-objective
• Scheduling

This paper proposes several novel hybrid ant colony optimization (ACO)-based algorithms to resolve multi-objective job-shop scheduling problem with equal-size lot splitting. The main issue discussed in this paper is lot-splitting of jobs and tradeoff between lot-splitting costs and makespan. One of the disadvantages of ACO is its uncertainty on time of convergence. In order to enrich search patterns of ACO and improve its performance, five enhancements are made in the proposed algorithms including: A new type of pheromone and greedy heuristic function; Three new functions of state transition rules; A nimble local search algorithm for the improvements of solution quality; Mutation mechanism for divisive searching; A particle swarm optimization (PSO)-based algorithm for adaptive tuning of parameters. The objectives that are used to measure the quality of the generated schedules are weighted-sum of makespan, tardiness of jobs and lot-splitting cost. The developed algorithms are analyzed extensively on real-world data obtained from a printing company and simulated data. A mathematical programming model is developed and paired-samples t-tests are performed between obtained solutions of mathematical programming model and proposed algorithms in order to verify effectiveness of proposed algorithms.

• 出版日期2017-8