Article ID: | iaor201353 |
Volume: | 24 |
Issue: | 1 |
Start Page Number: | 111 |
End Page Number: | 134 |
Publication Date: | Jan 2013 |
Journal: | IMA Journal of Management Mathematics |
Authors: | Wu Cheng, Zhang Rui |
Keywords: | heuristics: local search |
The job shop scheduling problem (JSSP) is a notoriously difficult problem in combinatorial optimization. Up till now, neighbourhood search has been the most efficient optimization framework for solving the problem. The discovery and innovative application of neighbourhood properties is a key issue in the design of such algorithms. Effective neighbourhood properties help one to exclude unpromising solutions in the neighbourhood, and thus accelerate the convergence of the whole searching process. In this paper, we aim at solving the JSSP with the objective of minimizing total weighted tardiness, which includes most other regular objective functions as special cases. A neighbourhood property of the problem is discovered based on the duality of linear programming models. Then, the neighbourhood property is utilized by a tree search procedure, which is finally embedded into the particle swarm optimization framework. According to extensive computational experiments and the real‐world application to a large‐scale manufacturing firm in China, the proposed approach is effective for solving the JSSP.