A neighbourhood property for the job shop scheduling problem with application to hybrid particle swarm optimization

A neighbourhood property for the job shop scheduling problem with application to hybrid particle swarm optimization

0.00 Avg rating0 Votes
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: ,
Keywords: heuristics: local search
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.