Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/65304
Title: Improved algorithms for single-machine serial-batch scheduling with rejection to minimize total completion time and total rejection cost
Authors: Yin, Y
Cheng, TCE 
Wang, D
Wu, CC
Keywords: Batch scheduling
Bicriterion scheduling
Dynamic programming
Rejection
Total completion time
Issue Date: 2016
Publisher: Institute of Electrical and Electronics Engineers
Source: IEEE transactions on systems, man, and cybernetics. Part A, Systems and humans, 2016, v. 46, no. 11, 7364271, p. 1578-1588 How to cite?
Journal: IEEE transactions on systems, man, and cybernetics. Part A, Systems and humans 
Abstract: Recently, Shabtay considered a scheduling problem on a single serial-batching machine with rejection to minimize the dual criteria of total completion time and total rejection cost, where the number of jobs to be included in each batch is not restricted. He studied four variants of the problem: the first is to minimize the sum of the two criteria; the second and third are to minimize one criterion, subject to the other criterion not exceeding a given value; and the last is to find the Pareto-optimal solutions for the bicriterion problem. Shabtay provided an O(n5) algorithm for the first variant and an O(n6/ϵ2) fully polynomial-time approximation scheme (FPTAS) for the fourth variant. In this paper, we provide an alternative O(n4) algorithm to solve the first variant and an O(n5/ϵ) FPTAS for the fourth variant, which are more efficient than those developed by Shabtay from a theoretical perspective. However, when the size of each batch is bounded by a given number b > 1, the corresponding time complexities of our algorithms for the first and fourth variants reduce to O(bn3) and O(bn4/ϵ), respectively.
URI: http://hdl.handle.net/10397/65304
ISSN: 1083-4427
EISSN: 1083-4419
DOI: 10.1109/TSMC.2015.2505644
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

1
Last Week
0
Last month
Citations as of Sep 26, 2017

WEB OF SCIENCETM
Citations

1
Last Week
0
Last month
Citations as of Sep 22, 2017

Page view(s)

15
Checked on Sep 24, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.