Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/31929
Title: Batch scheduling with controllable setup and processing times to minimize total completion time
Authors: Ng, CTD 
Cheng, TCE 
Kovalyov, MY
Keywords: Batching
Controllable setup and processing times
Minimizing total completion time
Scheduling
Single machine
Issue Date: 2003
Publisher: Palgrave Macmillan
Source: Journal of the Operational Research Society, 2003, v. 54, no. 5, p. 499-506 How to cite?
Journal: Journal of the Operational Research Society 
Abstract: We study a problem of scheduling n jobs on a single machine in batches. A batch is a set of jobs processed contiguously and completed together when the processing of all jobs in the batch is finished. Processing of a batch requires a machine setup time dependent on the position of this batch in the sequence. Setup times and job processing times are continuously controllable, that is, they are real-valued variables within their lower and upper bounds. A deviation of a setup time or job processing time from its upper bound is called a compression. The problem is to find a job sequence, its partition into batches, and the values for setup times and job processing times such that (a) total job completion time is minimized, subject to an upper bound on total weighted setup time and job processing time compression, or (b) a linear combination of total job completion time, total setup time compression, and total job processing time compression is minimized. Properties of optimal solutions are established. If the lower and upper bounds on job processing times can be similarly ordered or the job sequence is fixed, then O(n3 log n) and O(n5) time algorithms are developed to solve cases (a) and (b), respectively. If all job processing times are fixed or all setup times are fixed, then more efficient algorithms can be devised to solve the problems.
URI: http://hdl.handle.net/10397/31929
ISSN: 0160-5682
EISSN: 1476-9360
DOI: 10.1057/palgrave.jors.2601537
Appears in Collections:Journal/Magazine Article

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

SCOPUSTM   
Citations

7
Last Week
0
Last month
0
Citations as of Oct 8, 2017

WEB OF SCIENCETM
Citations

7
Last Week
0
Last month
0
Citations as of Oct 15, 2017

Page view(s)

86
Last Week
0
Last month
Checked on Oct 15, 2017

Google ScholarTM

Check

Altmetric



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