文章基本信息

标题：Critical paths of non-permutation and permutation flow shop scheduling problems
本地全文：下载
作者：Rossit, D. ; Tohmé, F. ; Frutos, M. 等
期刊名称：International Journal of Industrial Engineering Computations
印刷版ISSN：1923-2926
电子版ISSN：1923-2934
出版年度：2020
卷号：11
期号：2
页码：281-298
DOI：10.5267/j.ijiec.2019.8.001
语种：English
出版社：Growing Science Publishing Company
摘要：The literature on flow shop scheduling has extensively analyzed two classes of problems: permutation and non-permutation ones (PFS and NPFS). Most of the papers in this field have been just devoted on comparing the solutions obtained in both approaches. Our contribution consists of analyzing the structure of the critical paths determining the makespan of both kinds of schedules for the case of 2 jobs and m machines. We introduce a new characterization of the critical paths of PFS solutions as well as a decomposition procedure, yielding a representation of NPFS solutions as sequences of partial PFS ones. In structural comparisons we find cases in which NPFS solutions are dominated by PFS solutions. Numerical comparisons indicate that a wider dispersion of processing times improves the chances of obtaining optimal non-permutation schedules, in particular when this dispersion affects only a few machines.
关键词：Non-permutation flow shop; Scheduling; Makespan; Critical path