Memetic algorithms for solving job-shop scheduling problems

Title: Memetic algorithms for solving job-shop scheduling problems
Creator: Hasan, S. M. Kamrul; Sarker, Ruhul; Essam, Daryl; Cornforth, David
Relation: Memetic Computing Vol. 1, Issue 1, p. 69-83
Publisher Link: http://dx.doi.org/10.1007/s12293-008-0004-5
Publisher: Springer
Resource Type: journal article
Date: 2009
Description: The job-shop scheduling problem is well known for its complexity as an NP-hard problem. We have considered JSSPs with an objective of minimizing makespan while satisfying a number of hard constraints. In this paper, we developed a memetic algorithm (MA) for solving JSSPs. Three priority rules were designed, namely partial re-ordering, gap reduction and restricted swapping, and used as local search techniques in our MA. We have solved 40 benchmark problems and compared the results obtained with a number of established algorithms in the literature. The experimental results show that MA, as compared to GA, not only improves the quality of solutions but also reduces the overall computational time.
Subject: job-shop scheduling; genetic algorithm; memetic algorithm; local search; priority rules
Identifier: http://hdl.handle.net/1959.13/1057723
Identifier: uon:16247
Identifier: ISSN:1865-9284
Language: eng
Reviewed

		Thumbnail	File	Description	Size	Format