Two-stage no-wait proportionate flow shop scheduling with minimal service time variation and optional job rejection

Christos Koulamas and George J. Kyparisis

European Journal of Operational Research, 2023, vol. 305, issue 2, 608-616

Abstract: We consider two-stage no-wait proportionate flow shops with the objective of minimizing service time variation measured by defining the mid-processing point of a job and minimizing the Total Absolute Deviation of mid-processing Points (TADZ). We show that the two-stage no-wait proportionate flow shop with the TADZ objective is solvable in O(nlogn) time. Our findings provide an affirmative answer to an open research question posed by Kovalev et al. (2019) regarding existence of a solvable variant of the two-stage no-wait proportionate flow shop problem with the Total Absolute Deviation of Completion Times (TADC) objective. Moreover, we show when a generic two-stage no-wait proportionate flow shop scheduling problem is solvable in O(nlogn) time. We present practical applications where TADZ is more suitable than TADC as a scheduling objective. We also introduce a new metric defined as the sum of all partial schedule lengths SPSL and show that the two-stage no-wait proportionate flow shop with the SPSL objective is solvable in O(nlogn) time; thus, an additional solvable variant of the two-stage no-wait proportionate flow shop with the SPSL objective is identified and solved. Finally, we consider the option of rejecting a job from the schedule by paying a job-specific penalty for each rejected job and solve the resulting problem with the TADZ objective and the rejection option in O(n3) time by dynamic programming.

Keywords: Scheduling; “no-wait”; Flow shop; Proportionate; Rejection (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221722005008
Full text for ScienceDirect subscribers only

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:eee:ejores:v:305:y:2023:i:2:p:608-616

DOI: 10.1016/j.ejor.2022.06.025

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().