Exact algorithms and approximation schemes for proportionate flow shop scheduling with step-deteriorating processing times

Dvir Shabtay () and Baruch Mor ()
Additional contact information
Dvir Shabtay: Ben-Gurion University of the Negev
Baruch Mor: Ariel University

Journal of Scheduling, 2024, vol. 27, issue 3, No 3, 239-256

Abstract: Abstract We study two scheduling problems in a proportionate flow shop environment, where job processing times are machine independent. In contrast to classical proportionate flow shop models, we assume (in both problems) that processing times are step-deteriorating. Accordingly, each job $$J_{j}$$ J j has a normal processing time, $$a_{j}$$ a j , if it starts to be processed in the shop no later than its deteriorating date, $$\delta _{j}$$ δ j . Otherwise, the job’s processing time increases by $$b_{j}$$ b j (the job’s deterioration penalty). Our aim is to find a job schedule that minimizes either the makespan or the total load. These two problems are known to be $$\mathcal{N}\mathcal{P}$$ N P -hard for the special case of a single machine, even when all jobs have the same deteriorating date. In this paper, we derive several positive results in relation to the two problems. We first show that the two problems can be represented in a unified way. We then prove that the unified problem is only ordinary $$ \mathcal{N}\mathcal{P}$$ N P -hard by providing a pseudo-polynomial time algorithm for its solution. We also show that the pseudo-polynomial time algorithm can be converted into a fully polynomial time approximation scheme (FPTAS). Finally, we analyze the parameterized complexity of the problem with respect to the number of different deteriorating dates in the instance, $$v_{\delta }$$ v δ . We show that although the problem is $$\mathcal{N}\mathcal{P}$$ N P -hard when $$v_{\delta }=1$$ v δ = 1 , it is fixed parameterized tractable (FPT) for the combined parameters (i) $$(\nu _{\delta },\nu _{a})$$ ( ν δ , ν a ) and (ii) $$(\nu _{\delta },\nu _{b})$$ ( ν δ , ν b ) , where $$\nu _{a}$$ ν a is the number of different normal processing times in the instance, and $$\nu _{b}$$ ν b is the number of different deterioration penalties in the instance.

Keywords: Proportionate flow shop; Step deterioration; $$\mathcal{N}\mathcal{P}$$ N P -hardness; Approximation schemes; Fixed parameter tractability (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10951-022-00766-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:jsched:v:27:y:2024:i:3:d:10.1007_s10951-022-00766-2

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-022-00766-2

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().