Journal
FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE
Volume 25, Issue 6, Pages 654-661Publisher
ELSEVIER
DOI: 10.1016/j.future.2009.01.004
Keywords
Scheduling; Job shop; Sequence-dependent set-up time; Variable neighborhood search; Variable neighborhood descent; Insertion neighborhood
Categories
Ask authors/readers for more resources
Production Scheduling problems are typically named bases on the processing routes of their jobs on different processors and also the number of processors in each stage. In this paper, we consider the problem of scheduling a job shop (JSS) where set-up times are sequence-dependent (SDST) to minimize the maximum completion times of operations or makespan. Our problem is generally formulated as J/STsd/C-max. To tackle Such an NP-hard problem, a recent effective metaheuristic algorithm known as variable neighborhood search (VNS) is employed. VNS algorithms have shown excellent capability to solve scheduling problems to optimal or near-optimal schedule. Our proposed VNS is readily intelligible yet is a robust Solution technique for the problem of SDST JSS. VNS is categorized as a local search-based algorithm armed with systematic neighborhood search structures. Our proposed VNS obviates the notorious myopic behavior of local search-based metaheuristic algorithms by the means of several systematic insertion neighborhood search structures. An experimental design based on Taillard's benchmark is conducted to evaluate the efficiency and effectiveness of our proposed algorithm against some effective algorithms in the literature. The obtained results strongly support the high performance of our proposed algorithm with respect to other well-known heuristic and metaheuristic algorithms. (c) 2009 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available