Flow-shop scheduling with exact delays to minimize makespan

Khatami, M; Salehipour, A; Cheng, TCE

Flow-shop scheduling with exact delays to minimize makespan

Khatami, M

Salehipour, A Cheng, TCE

Permalink

Publisher:: PERGAMON-ELSEVIER SCIENCE LTD
Publication Type:: Journal Article
Citation:: Computers and Industrial Engineering, 2023, 183
Issue Date:: 2023-09-01

Recently Added

	Filename	Description	Size
	1-s2.0-S0360835223004801-main.pdf	Published version	626.04 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is new to OPUS and is not currently available.

Full metadata record

Field	Value	Language
dc.contributor.author	Khatami, M https://orcid.org/0000-0001-6159-9772
dc.contributor.author	Salehipour, A
dc.contributor.author	Cheng, TCE
dc.date.accessioned	2024-05-03T03:13:41Z
dc.date.available	2024-05-03T03:13:41Z
dc.date.issued	2023-09-01
dc.identifier.citation	Computers and Industrial Engineering, 2023, 183
dc.identifier.issn	0360-8352
dc.identifier.issn	1879-0550
dc.identifier.uri	http://hdl.handle.net/10453/178588
dc.description.abstract	The flow-shop scheduling problem with exact delays is generalization of no-wait flow-shop scheduling in which an exact delay exists between the consecutive tasks of each job. The problem with distinct delays to minimize the makespan is strongly NP-hard even for the two-machine case with unit execution time tasks. Providing polynomial-time solutions for special cases of the problem, we show that the two-machine permutation flow-shop case is solvable in O(nlogn) time, while the case with more than two machines is strongly NP-hard. We also show that the multi-machine case with delays following the ordered structure possesses the pyramidal-shaped property and propose an O(n2)-time dynamic program to solve it. We further improve the time complexity of the solution algorithm to O(nlogn) under certain conditions.
dc.language	English
dc.publisher	PERGAMON-ELSEVIER SCIENCE LTD
dc.relation	http://purl.org/au-research/grants/arc/DE170100234
dc.relation.ispartof	Computers and Industrial Engineering
dc.relation.isbasedon	10.1016/j.cie.2023.109456
dc.rights	info:eu-repo/semantics/restrictedAccess
dc.subject	01 Mathematical Sciences, 08 Information and Computing Sciences, 09 Engineering
dc.subject.classification	Industrial Engineering & Automation
dc.subject.classification	40 Engineering
dc.subject.classification	46 Information and computing sciences
dc.subject.classification	49 Mathematical sciences
dc.title	Flow-shop scheduling with exact delays to minimize makespan
dc.type	Journal Article
utslib.citation.volume	183
utslib.for	01 Mathematical Sciences
utslib.for	08 Information and Computing Sciences
utslib.for	09 Engineering
pubs.organisational-group	University of Technology Sydney
pubs.organisational-group	University of Technology Sydney/Faculty of Design, Architecture and Building
pubs.organisational-group	University of Technology Sydney/Faculty of Design, Architecture and Building/School of Built Environment
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	recently_added	*
dc.rights.license	This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/bync-nd/4.0/).
dc.date.updated	2024-05-03T03:13:40Z
pubs.publication-status	Published
pubs.volume	183

Abstract:

The flow-shop scheduling problem with exact delays is generalization of no-wait flow-shop scheduling in which an exact delay exists between the consecutive tasks of each job. The problem with distinct delays to minimize the makespan is strongly NP-hard even for the two-machine case with unit execution time tasks. Providing polynomial-time solutions for special cases of the problem, we show that the two-machine permutation flow-shop case is solvable in O(nlogn) time, while the case with more than two machines is strongly NP-hard. We also show that the multi-machine case with delays following the ordered structure possesses the pyramidal-shaped property and propose an O(n2)-time dynamic program to solve it. We further improve the time complexity of the solution algorithm to O(nlogn) under certain conditions.

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

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