Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/31586
Title: Batch scheduling in the no-wait two-machine flowshop to minimize the makespan
Authors: Lin, BMT
Cheng, TCE 
Keywords: Batching
Computational complexity
Flowshop scheduling
Makespan
No-wait
Issue Date: 2001
Publisher: Pergamon Press
Source: Computers and operations research, 2001, v. 28, no. 7, p. 613-624 How to cite?
Journal: Computers and operations research 
Abstract: We consider a scheduling problem where a set of jobs are simultaneously available for processing in a no-wait two-machine flowshop. The objective is to minimize the makespan, i.e. the maximum completion time of the jobs. The operations of all jobs are processed on both machines in batches. A constant setup time is incurred whenever a batch is formed on the machines. The processing time of a batch is defined as the setup time plus the sum of all processing times of the jobs it contains. The completion time of a job is defined as the time at which the batch containing it is completely processed on machine two. The no-wait scheduling problem in the two-machine flowshop without batching is known as polynomially solvable. We show that several restricted versions of the problem under study in this paper are strongly N P-hard, which imply that the general problem is also strongly N P-hard. We then establish some interesting properties and exploit them to design solution methods for two special cases.
URI: http://hdl.handle.net/10397/31586
ISSN: 0305-0548
EISSN: 1873-765X
DOI: 10.1016/S0305-0548(99)00138-0
Appears in Collections:Journal/Magazine Article

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

SCOPUSTM   
Citations

28
Last Week
0
Last month
0
Citations as of Aug 19, 2017

WEB OF SCIENCETM
Citations

22
Last Week
0
Last month
Citations as of Aug 21, 2017

Page view(s)

55
Last Week
3
Last month
Checked on Aug 21, 2017

Google ScholarTM

Check

Altmetric



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