Proportionate Flow Shop Scheduling with Rejection

Shi-Sheng Li, Qian De-Liang () and Ren-Xia Chen ()
Additional contact information
Shi-Sheng Li: Department of Information and Computation Science, Zhongyuan University of Technology, Zhengzhou 450007, P. R. China
Qian De-Liang: Department of Information and Computation Science, Zhongyuan University of Technology, Zhengzhou 450007, P. R. China
Ren-Xia Chen: Department of Information and Computation Science, Zhongyuan University of Technology, Zhengzhou 450007, P. R. China

Asia-Pacific Journal of Operational Research (APJOR), 2017, vol. 34, issue 04, 1-13

Abstract: We consider the problem of scheduling n jobs with rejection on a set of m machines in a proportionate flow shop system where the job processing times are machine-independent. The goal is to find a schedule to minimize the scheduling cost of all accepted jobs plus the total penalty of all rejected jobs. Two variations of the scheduling cost are considered. The first is the maximum tardiness and the second is the total weighted completion time. For the first problem, we first show that it is 𝒩𝒫-hard, then we construct a pseudo-polynomial time algorithm to solve it and an O(n3log n) time for the case where the jobs have the same processing time. For the second problem, we first show that it is 𝒩𝒫-hard, then we design O(n2) time algorithms for the case where the jobs have the same weight and for the case where the jobs have the same processing time.

Keywords: Proportionate flow shop; rejection; computational complexity (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595917500154
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:34:y:2017:i:04:n:s0217595917500154

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595917500154

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