A divide-and-conquer strategy with particle swarm optimization for the job shop scheduling problem

Abstract

An optimization algorithm based on the ‘divide-and-conquer’ methodology is proposed for solving large job shop scheduling problems with the objective of minimizing total weighted tardiness. The algorithm adopts a non-iterative framework. It first searches for a promising decomposition policy for the operation set by using a simulated annealing procedure in which the solutions are evaluated with reference to the upper bound and the lower bound of the final objective value. Subproblems are then constructed according to the output decomposition policy and each subproblem is related to a subset of operations from the original operation set. Subsequently, all these subproblems are sequentially solved by a particle swarm optimization algorithm, which leads directly to a feasible solution to the original large-scale scheduling problem. Numerical computational experiments are carried out for both randomly generated test problems and the real-world production data from a large speed-reducer factory in China. Results show that the proposed algorithm can achieve satisfactory solution quality within reasonable computational time for large-scale job shop scheduling problems.

Keywords:

• job shop scheduling problem
• divide and conquer
• simulated annealing
• particle swarm optimization

Acknowledgements

The article is supported by the National 973 Basic Research Program of China (No. 2002CB312202), the National 863 High-Tech Program of China (No. 2007AA04Z102, No. 2006AA04Z163), the National Natural Science Foundation of China (No. 60834004, No. 60721003) and the Program for New Century Excellent Talents in University.

Notes

If C _j is used to denote the completion time of job j, then (also referred to as the ‘makespan’) represents the earliest time by which all the n jobs have been completed. ‘Minimize C _max ’ is the most frequently adopted objective function in the earlier studies of JSSPs.

According to the explanation of the three-field notation in Section 2, denotes the standard job shop scheduling problem with the makespan criterion.

This is in fact a strengthening of the second property mentioned in Subsection 4.1 of a decomposition policy. In this strengthened version, if, under the adopted decomposition policy, operations i ₁ and i ₂ which are to be processed by the same machine satisfy and l ₁<l ₂, then the direction of the original disjunctive arc (i ₁, i ₂) is fixed as pointing from i ₁ to i ₂ (inspired by the fact that subset has a higher scheduling priority than subset ), and, subsequently, this is noted as .

The optimal schedule for problem can be obtained by sorting all the jobs in non-decreasing order of their release times {r _j } (Brucker 2004, Section 4.2).

In PSO, a ‘position’ is equivalent to a solution in the search space.

This is because the objective function used for solving each subproblem (especially the subproblems that are solved earlier) usually cannot exactly reflect the characteristics of the final (overall) objective function. Over-optimization of subproblems may occur in many decomposition-based optimization methodologies.

Available from the web at http://people.brunel.ac.uk/~mastjjb/jeb/info.html