Coordinating scheduling and rejection decisions in a two-machine flow shop scheduling problem

Dvir Shabtay and Enrique Gerstl

European Journal of Operational Research, 2024, vol. 316, issue 3, 887-898

Abstract: We study a two-machine flow shop scheduling problem where any operation can be rejected at a certain cost. A solution for such a problem requires two sets of decisions. The first involves the partition of the set of operations into two subsets: the set of operations that are accepted for scheduling in the shop, and the set of rejected operations. The second decision involves scheduling the set of accepted operations in the shop. The objective is to find a solution that minimizes the sum of the makespan and the total rejection cost. We prove that the problem is NP-hard even if all processing operations have identical processing times and identical rejection costs on either one of the two machines. We show, however, that the problem is fixed parameterized tractable with respect to a parameter that combine the number of different processing times on both machines with the number of different rejection costs on one out of the two machines. We also provide a pseudo-polynomial time algorithm for the problem, which we then convert into a fully polynomial time approximation scheme. This is achieved by dividing the problem into a set of subproblems and deriving a fully polynomial time approximation scheme for each one of them, separately. Finally, we present an integer linear programming formulation of the problem and two simple 2-approximation algorithms.

Keywords: Scheduling; Flow shop; Approximation algorithms; Rejection; Integer linear programming (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221724002212
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:316:y:2024:i:3:p:887-898

DOI: 10.1016/j.ejor.2024.03.021

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 ().