A Simulated Annealing-Based Heuristic Algorithm for Job Shop Scheduling to Minimize Lateness
Open Access
- 1 January 2013
- journal article
- research article
- Published by SAGE Publications in International Journal of Advanced Robotic Systems
- Vol. 10 (4), 214
- https://doi.org/10.5772/55956
Abstract
A decomposition-based optimization algorithm is proposed for solving large job shop scheduling problems with the objective of minimizing the maximum lateness. First, we use the constraint propagation theory to derive the orientation of a portion of disjunctive arcs. Then we use a simulated annealing algorithm to find a decomposition policy which satisfies the maximum number of oriented disjunctive arcs. Subsequently, each subproblem (corresponding to a subset of operations as determined by the decomposition policy) is successively solved with a simulated annealing algorithm, which leads to a feasible solution to the original job shop scheduling problem. Computational experiments are carried out for adapted benchmark problems, and the results show the proposed algorithm is effective and efficient in terms of solution quality and time performance.Keywords
This publication has 26 references indexed in Scilit:
- Scheduling Trains with Priorities: A No-Wait Blocking Parallel-Machine Job-Shop Scheduling ModelTransportation Science, 2011
- Scheduling a dynamic job shop production system with sequence-dependent setups: An experimental studyRobotics and Computer-Integrated Manufacturing, 2008
- Operation-based flowtime estimation in a dynamic job shopOmega, 2002
- Due Date Assignment, Job Order Release, and Sequencing Interaction in Job Shop Scheduling*Decision Sciences, 1992
- Dynamic job shop scheduling: A survey of simulation researchOmega, 1990
- An Algorithm for Solving the Job-Shop ProblemManagement Science, 1989
- The Shifting Bottleneck Procedure for Job Shop SchedulingManagement Science, 1988
- Sequencing Rules and Due-Date Assignments in a Job ShopManagement Science, 1984
- Priority dispatching with operation due dates in a job shopJournal of Operations Management, 1982
- Priority dispatching rules in job shops with assembly operations and random delaysOmega, 1980