Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/21867
Title: Batch scheduling and common due-date assignment on a single machine
Authors: Cheng, TCE 
Kovalyov, MY
Keywords: Batching
Due-date assignment
Dynamic programming
Fully polynomial approximation scheme
Scheduling
Issue Date: 1996
Source: Discrete applied mathematics, 1996, v. 70, no. 3, p. 231-245 How to cite?
Journal: Discrete Applied Mathematics 
Abstract: We consider the problem of scheduling n groups of jobs on a single machine where three types of decisions are combined: scheduling, batching and due-date assignment. Each group includes identical jobs and may be split into batches; jobs within each batch are processed jointly. A sequence independent machine set-up time is needed between each two consecutively scheduled batches of different groups. A due-date common to all jobs has to be assigned. A schedule specifies the size of each batch, i.e. the number of jobs it contains, and a processing order for the batches. The objective is to determine a value for the common due-date and a schedule so as to minimize the sum of the due date assignment penalty and the weighted number of tardy jobs. Several special cases of this problem are shown to be ordinary NP-hard. Some cases are solved in O(n log n) time. Two pseudopolynomial dynamic programming algorithms are presented for the general problem, as well as a fully polynomial approximation scheme.
URI: http://hdl.handle.net/10397/21867
ISSN: 0166-218X
DOI: 10.1016/0166-218X(96)80468-9
Appears in Collections:Journal/Magazine Article

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

SCOPUSTM   
Citations

18
Last Week
0
Last month
0
Citations as of Sep 24, 2017

WEB OF SCIENCETM
Citations

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

Page view(s)

77
Last Week
2
Last month
Checked on Sep 18, 2017

Google ScholarTM

Check

Altmetric



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