On a borderline between the NP-hard and polynomial-time solvable cases of the flow shop with job-dependent storage requirements

Kononov, A; Memar, J; Zinder, Y

On a borderline between the NP-hard and polynomial-time solvable cases of the flow shop with job-dependent storage requirements

Kononov, A Memar, J

Zinder, Y

Permalink

Publisher:: Springer Science and Business Media LLC
Publication Type:: Journal Article
Citation:: Journal of Global Optimization, 2022, 83, (3), pp. 445-456
Issue Date:: 2022-01-01

Closed Access

	Filename	Description	Size
	s10898-021-01097-w.pdf		271.55 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Kononov, A
dc.contributor.author	Memar, J https://orcid.org/0000-0003-2395-1450
dc.contributor.author	Zinder, Y https://orcid.org/0000-0003-2024-8129
dc.date.accessioned	2023-01-31T02:10:46Z
dc.date.available	2023-01-31T02:10:46Z
dc.date.issued	2022-01-01
dc.identifier.citation	Journal of Global Optimization, 2022, 83, (3), pp. 445-456
dc.identifier.issn	0925-5001
dc.identifier.issn	1573-2916
dc.identifier.uri	http://hdl.handle.net/10453/165645
dc.description.abstract	The paper is concerned with the two-machine flow shop, where each job requires an additional resource (referred to as storage space) from the start of its first operation till the end of its second operation. The storage requirement of a job is determined by the processing time of its first operation. At any point in time, the total consumption of this additional resource cannot exceed a given limit (referred to as the storage capacity). The goal is to minimise the makespan, i.e. to minimise the time needed for the completion of all jobs. This problem is NP-hard in the strong sense. The paper analyses how the parameter - a lower bound on the storage capacity specified in terms of the processing times, affects the computational complexity.
dc.language	en
dc.publisher	Springer Science and Business Media LLC
dc.relation.ispartof	Journal of Global Optimization
dc.relation.isbasedon	10.1007/s10898-021-01097-w
dc.rights	info:eu-repo/semantics/closedAccess
dc.subject	0102 Applied Mathematics, 0103 Numerical and Computational Mathematics, 0802 Computation Theory and Mathematics
dc.subject.classification	Operations Research
dc.title	On a borderline between the NP-hard and polynomial-time solvable cases of the flow shop with job-dependent storage requirements
dc.type	Journal Article
utslib.citation.volume	83
utslib.for	0102 Applied Mathematics
utslib.for	0103 Numerical and Computational Mathematics
utslib.for	0802 Computation Theory and Mathematics
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	closed_access	*
pubs.consider-herdc	false
dc.date.updated	2023-01-31T02:10:42Z
pubs.issue	3
pubs.publication-status	Published online
pubs.volume	83
utslib.citation.issue	3

Abstract:

The paper is concerned with the two-machine flow shop, where each job requires an additional resource (referred to as storage space) from the start of its first operation till the end of its second operation. The storage requirement of a job is determined by the processing time of its first operation. At any point in time, the total consumption of this additional resource cannot exceed a given limit (referred to as the storage capacity). The goal is to minimise the makespan, i.e. to minimise the time needed for the completion of all jobs. This problem is NP-hard in the strong sense. The paper analyses how the parameter - a lower bound on the storage capacity specified in terms of the processing times, affects the computational complexity.

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

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