Makespan minimization for the m-machine ordered flow shop scheduling problem

Khatami, M; Salehipour, A; Hwang, FJ

Makespan minimization for the m-machine ordered flow shop scheduling problem

Khatami, M

Salehipour, A

Hwang, FJ

Permalink

Publication Type:: Journal Article
Citation:: Computers and Operations Research, 2019, 111 pp. 400 - 414
Issue Date:: 2019-11-01

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

The embargo period expires on 1 Jul 2022

Adobe PDF

Download Accepted Manuscript VersionAdobe PDF (876.03 kB)

View on publisher's site

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Khatami, M https://orcid.org/0000-0001-6159-9772	en_US
dc.contributor.author	Salehipour, A https://orcid.org/0000-0003-4866-1396	en_US
dc.contributor.author	Hwang, FJ https://orcid.org/0000-0002-1741-5590	en_US
dc.date.issued	2019-11-01	en_US
dc.identifier.citation	Computers and Operations Research, 2019, 111 pp. 400 - 414	en_US
dc.identifier.issn	0305-0548	en_US
dc.identifier.uri	http://hdl.handle.net/10453/134448
dc.description.abstract	© 2019 As a subcategory of the classical flow shop scheduling problem, the ordered flow shop scheduling problem deals with the case where processing times follow a specific structure. This study addresses the m-machine n-job ordered flow shop problem with the objective of minimizing the makespan, which is known to be NP-hard. Two efficient heuristics, and one fast iterated local search algorithm are proposed. The algorithms are developed by utilizing the pyramidal-shaped property of the problem. To the best of our knowledge, there has been no benchmark instances published for the ordered flow shop scheduling problem. This study first generates three sets of benchmarks consisting of 600 instances in total, ranging from 10 to 800 jobs and 5 to 60 machines. The algorithms are tested on those instances. The outcomes demonstrate the efficiency and effectiveness of the proposed algorithms, in particular, the iterated local search algorithm in solving the ordered flow shop scheduling problem. The solutions are also compared with those of the best available algorithm for the permutation flow shop problem, and it is shown that the Iterated Local Search performs better. We also discuss the suitability of the proposed algorithms for scheduling problems with the V-shaped property.	en_US
dc.relation.ispartof	Computers and Operations Research	en_US
dc.relation.isbasedon	10.1016/j.cor.2019.06.012	en_US
dc.rights	info:eu-repo/semantics/embargoedAccess
dc.subject.classification	Operations Research	en_US
dc.title	Makespan minimization for the m-machine ordered flow shop scheduling problem	en_US
dc.type	Journal Article
utslib.citation.volume	111	en_US
utslib.for	0102 Applied Mathematics	en_US
utslib.for	0103 Numerical and Computational Mathematics	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Science
pubs.organisational-group	/University of Technology Sydney/Faculty of Science/School of Mathematical and Physical Sciences
utslib.copyright.status	open_access	*
utslib.copyright.embargo	2022-07-01T00:00:00+1000
pubs.publication-status	Published	en_US
pubs.volume	111	en_US

Abstract:

© 2019 As a subcategory of the classical flow shop scheduling problem, the ordered flow shop scheduling problem deals with the case where processing times follow a specific structure. This study addresses the m-machine n-job ordered flow shop problem with the objective of minimizing the makespan, which is known to be NP-hard. Two efficient heuristics, and one fast iterated local search algorithm are proposed. The algorithms are developed by utilizing the pyramidal-shaped property of the problem. To the best of our knowledge, there has been no benchmark instances published for the ordered flow shop scheduling problem. This study first generates three sets of benchmarks consisting of 600 instances in total, ranging from 10 to 800 jobs and 5 to 60 machines. The algorithms are tested on those instances. The outcomes demonstrate the efficiency and effectiveness of the proposed algorithms, in particular, the iterated local search algorithm in solving the ordered flow shop scheduling problem. The solutions are also compared with those of the best available algorithm for the permutation flow shop problem, and it is shown that the Iterated Local Search performs better. We also discuss the suitability of the proposed algorithms for scheduling problems with the V-shaped property.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/134448