Non-permutation flowshop scheduling problem with minimal and maximal time lags: theoretical study and heuristic

E. Dhouib (), J. Teghem () and T. Loukil ()
Additional contact information
E. Dhouib: Unité de recherche LOgistique Gestion Industrielle et de la Qualité (LOGIQ), Institut Supérieur de Gestion Industrielle de Sfax, Université de Sfax
J. Teghem: Service de Mathématique et de Recherche Opérationnelle (MathRO), Université de Mons/Faculté Polytechnique
T. Loukil: Unité de recherche LOgistique Gestion Industrielle et de la Qualité (LOGIQ), Institut Supérieur de Gestion Industrielle de Sfax, Université de Sfax

Annals of Operations Research, 2018, vol. 267, issue 1, No 7, 134 pages

Abstract: Abstract 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.

Keywords: Scheduling; Non-permutation flowshop; Time lags; Mathematical programming; Heuristics; Lexicographic optimization (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10479-018-2775-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:267:y:2018:i:1:d:10.1007_s10479-018-2775-5

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-018-2775-5

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().