| Download | - View accepted manuscript: A divide and conquer-based greedy search for two-machine no-wait job shop problems with makespan minimisation (PDF, 873 KiB)
|
|---|
| DOI | Resolve DOI: https://doi.org/10.1080/00207543.2011.582185 |
|---|
| Author | Search for: Zhu, Jie; Search for: Li, Xiaoping1; Search for: Shen, Weiming1 |
|---|
| Affiliation | - National Research Council of Canada. NRC Institute for Research in Construction
|
|---|
| Format | Text, Article |
|---|
| Subject | scheduling; no-wait; job shop; two-machine |
|---|
| Abstract | This 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 | 2011-07-12 |
|---|
| In | |
|---|
| Language | English |
|---|
| Peer reviewed | Yes |
|---|
| NRC number | NRCC 51701 |
|---|
| NPARC number | 20870258 |
|---|
| Export citation | Export as RIS |
|---|
| Report a correction | Report a correction (opens in a new tab) |
|---|
| Record identifier | b9e2422a-775a-48a0-bae9-77301e6e1d69 |
|---|
| Record created | 2012-10-29 |
|---|
| Record modified | 2020-04-21 |
|---|
