A divide and conquer-based greedy search for two-machine no-wait job shop problems with makespan minimisation

Download
  1. (PDF, 503 KB)
  2. Get@NRC: A divide and conquer-based greedy search for two-machine no-wait job shop problems with makespan minimisation (Opens in a new window)
DOIResolve DOI: http://doi.org/10.1080/00207543.2011.582185
AuthorSearch for: ; Search for: ; Search for:
TypeArticle
Journal titleInternational Journal of Production Research
ISSN0020-7543
Volume50
Issue10
Pages26922704; # of pages: 13
Subjectscheduling; no-wait; job shop; two-machine
AbstractThis paper addresses a two-machine no-wait job shop problem with makespan minimization. It is well known that this problem is strongly NP-hard. A divide-and-conquer approach (DC for short) is adopted to calculate the optimal timetable of a given sequence. It decomposes the given sequences into several independent parts and conquers them separately. A timetable enhancing method is introduced to further improve the timetable obtained by DC. It constructs a set of flow shop type jobs based on the result from DC and calculates the best timetable for these newly constructed jobs by the well-known Gilmore and Gomory method (GG for short). An efficient greedy search is proposed by integrating DC with GG to search for the best sequence. Experimental results show that the proposed algorithm can find the optimal solutions for 96% of the randomly generated test instances on average.
Publication date
LanguageEnglish
AffiliationNRC Institute for Research in Construction; National Research Council Canada
Peer reviewedYes
NRC number51701
NPARC number20870258
Export citationExport as RIS
Report a correctionReport a correction
Record identifierb9e2422a-775a-48a0-bae9-77301e6e1d69
Record created2012-10-29
Record modified2016-05-09
Bookmark and share
  • Share this page with Facebook (Opens in a new window)
  • Share this page with Twitter (Opens in a new window)
  • Share this page with Google+ (Opens in a new window)
  • Share this page with Delicious (Opens in a new window)