A fully polynomial time approximation scheme for scheduling on parallel identical two-stage openshops

Jianming Dong (), Ruyan Jin (), Jueliang Hu () and Guohui Lin ()
Additional contact information
Jianming Dong: Zhejiang Sci-Tech University
Ruyan Jin: Zhejiang Sci-Tech University
Jueliang Hu: Zhejiang Sci-Tech University
Guohui Lin: University of Alberta

Journal of Combinatorial Optimization, 2019, vol. 37, issue 2, No 15, 668-684

Abstract: Abstract A two-stage openshop consists of a machine in the first stage and a machine in the second stage; a job processed on the two-stage openshop means it is processed non-preemptively by each of the two machines, in whichever order. We consider the scheduling problem at the availability of multiple parallel identical two-stage openshops, with the goal to minimize the makespan. By uncovering the important role of the critical job in the optimal schedule on a two-stage openshop, we propose to sort the jobs in the novel critical-job order, and use this order to design a pseudo-polynomial time dynamic programming exact algorithm to solve our scheduling problem with any fixed number of two-stage openshops. Afterwards, using the standard scaling technique, we develop the dynamic programming algorithm into a fully polynomial-time approximation scheme. These results improve previously proposed constant ratio approximation algorithms.

Keywords: Scheduling; Two-stage openshop; Makespan; Dynamic programming; Fully polynomial-time approximation scheme (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-018-0314-6 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:jcomop:v:37:y:2019:i:2:d:10.1007_s10878-018-0314-6

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-018-0314-6

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

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