An improved ant colony optimization for solving the flexible job shop scheduling problem with multiple time constraints

Abstract

The flexible job shop scheduling problem is important in many research fields such as production management and combinatorial optimization, and it contains sub-problems of machine assignment and operation sequencing. In this paper, we study a many-objective FJSP (MaOFJSP) with multiple time constraints on setup time, transportation time and delivery time, with the objective of minimizing the maximum completion time, the total workload, the workload of critical machine and penalties of earliness/tardiness. Based on the given problem, an improved ant colony optimization is proposed to solve the problem. A distributed coding approach is proposed by the problem features. Three initialization methods are proposed to improve the quality and diversity of the initial solutions. The front end of the algorithm is designed to iteratively update the machine assignment to search for different neighborhoods. Then the improved ant colony optimization is used for local search of the neighborhood. For the searched scheduling set the entropy weight method and non-dominated sorting are used for filtering. Then mutation and closeness operations are proposed to improve the diversity of the solutions. The algorithm was evaluated through experiments based on 28 benchmark instances. The experimental results show that the algorithm can effectively solve the MaOFJSP problem.

Keywords

• many-objective flexible job-shop scheduling problem
• improved ant colony optimization
• setup time
• transportation time
• delivery time