| Téléchargement | - Voir le manuscrit accepté : A divide and conquer-based greedy search for two-machine no-wait job shop problems with makespan minimisation (PDF, 873 Kio)
|
|---|
| DOI | Trouver le DOI : https://doi.org/10.1080/00207543.2011.582185 |
|---|
| Auteur | Rechercher : Zhu, Jie; Rechercher : Li, Xiaoping1; Rechercher : Shen, Weiming1 |
|---|
| Affiliation | - Conseil national de recherches du Canada. Institut de recherche en construction du CNRC
|
|---|
| Format | Texte, Article |
|---|
| Sujet | scheduling; no-wait; job shop; two-machine |
|---|
| Résumé | 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. |
|---|
| Date de publication | 2011-07-12 |
|---|
| Dans | |
|---|
| Langue | anglais |
|---|
| Publications évaluées par des pairs | Oui |
|---|
| Numéro du CNRC | NRCC 51701 |
|---|
| Numéro NPARC | 20870258 |
|---|
| Exporter la notice | Exporter en format RIS |
|---|
| Signaler une correction | Signaler une correction (s'ouvre dans un nouvel onglet) |
|---|
| Identificateur de l’enregistrement | b9e2422a-775a-48a0-bae9-77301e6e1d69 |
|---|
| Enregistrement créé | 2012-10-29 |
|---|
| Enregistrement modifié | 2020-04-21 |
|---|
