Non-permutation flowshop scheduling problem with minimal and maximal time lags: theoretical study and heuristic
| Autor: | Jacques Teghem, Emna Dhouib, Taicir Loukil |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Mathematical optimization
Schedule 021103 operations research Job shop scheduling Computer science Heuristic Heuristic (computer science) 0211 other engineering and technologies General Decision Sciences Time lag 02 engineering and technology Management Science and Operations Research Scheduling (computing) Theory of computation 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Heuristics Computer Science::Operating Systems |
| Zdroj: | Annals of Operations Research. 267:101-134 |
| ISSN: | 1572-9338 0254-5330 |
| DOI: | 10.1007/s10479-018-2775-5 |
| Popis: | In this paper, we address the non-permutation flowshop scheduling problem with minimal and maximal time lags between successive operations of each job. For this problem, the set of permutation schedules is not a dominant set but not all non-permutation schedules are feasible because they are not always able to satisfy all time lag constraints. We present a theoretical study, limited to the two-machine case, and related to the change on one machine of the order of two successive jobs of a permutation schedule. This study gives first the necessary conditions to make such move with regard to the feasibility of the schedule; secondly the necessary conditions to make such move interesting with regard to either the makespan or the number of tardy jobs. Through this analysis, we obtain new properties of dominance of permutation schedules. The results of the study are incorporated into a heuristic algorithm which starts the search with optimal permutation schedules and tries to improve them so as to obtain better non-permutation schedules. We also propose a mixed integer linear programming model. The objective function is to minimize lexicographically the number of tardy jobs as primary criterion and the makespan as secondary one. Computational experiments are performed to compare permutation with non-permutation schedules. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
| Nepřihlášeným uživatelům se plný text nezobrazuje | K zobrazení výsledku je třeba se přihlásit. |