A PTAS for the multiple parallel identical multi-stage flow-shops to minimize the makespan

Weitian Tong, Eiji Miyano, Randy Goebel, Guohui Lin

Research output: Contribution to book or proceedingConference articlepeer-review

7 Scopus citations

Abstract

In the parallel k-stage flow-shops problem, we are given m identical k-stage flow-shops and a set of jobs. Each job can be processed by any one of the flow-shops but switching between flow-shops is not allowed. The objective is to minimize the makespan, which is the finishing time of the last job. This problem generalizes the classical parallel identical machine scheduling (where k = 1) and the classical flow-shop scheduling (where m = 1) problems, and thus it is NP-hard. We present a polynomial-time approximation scheme for the problem, when m and k are fixed constants. The key technique is to enumerate over schedules for big jobs, solve a linear programming for small jobs, and add the fractional small jobs at the end. Such a technique has been used in the design of similar approximation schemes.

Original languageEnglish
Title of host publicationFrontiers in Algorithmics - 10th International Workshop, FAW 2016, Proceedings
EditorsSergey Bereg, Daming Zhu
PublisherSpringer Verlag
Pages227-237
Number of pages11
ISBN (Print)9783319398167
DOIs
StatePublished - 2016
EventInternational Workshop on Frontiers in Algorithmics - Qingdao, China
Duration: Jun 30 2016Jul 2 2016
Conference number: 10
https://link.springer.com/book/10.1007/978-3-319-39817-4

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9711
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Workshop on Frontiers in Algorithmics
Abbreviated titleFAW
Country/TerritoryChina
CityQingdao
Period06/30/1607/2/16
Internet address

Scopus Subject Areas

  • Theoretical Computer Science
  • General Computer Science

Keywords

  • Flow-shop scheduling
  • Linear program
  • Makespan
  • Multiprocessor scheduling
  • Polynomial-time approximation scheme

Fingerprint

Dive into the research topics of 'A PTAS for the multiple parallel identical multi-stage flow-shops to minimize the makespan'. Together they form a unique fingerprint.

Cite this