TWO-STAGE FLOWSHOP SCHEDULING PROBLEMS WITH IDENTICAL AND BATCH PROCESSORS

Wen-Wei Wang, Long-Min He and Ming-Bao Cheng
Additional contact information
Wen-Wei Wang: Department of Mathematics, Shanghai University, Shanghai 200444, China
Long-Min He: Department of Mathematics, Shanghai University, Shanghai 200444, China
Ming-Bao Cheng: Management School, Guangdong University of Technology, Guangdong 510520, China

Asia-Pacific Journal of Operational Research (APJOR), 2010, vol. 27, issue 05, 617-627

Abstract: This paper considers minimizing total completion time in a two-stage flowshop scheduling problem withmidentical parallel machines at Stage 1 and a batch processor at Stage 2. We prove that the problem when all jobs have same processing time at Stage 2 isNP – hardand gave a two-approximation algorithm inO(n3)time. In the case that all jobs have arbitrary processing time at Stage 1 and at Stage 2, we give an approximation algorithm after pointing out that in this case the problem is stronglyNP – hard. Hundreds of instances of a numerical experiment show that the worst-case ratio of this approximation algorithm is nearing 2.

Keywords: Scheduling; flowshop; identical machine; batch processor; complexity; algorithm (search for similar items in EconPapers)
Date: 2010
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595910002909
Access to full text is restricted to subscribers

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:wsi:apjorx:v:27:y:2010:i:05:n:s0217595910002909

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595910002909

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().