Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/30725
Title: Single-machine scheduling with a common due window
Authors: Yeung, WK
Oguz, C
Cheng, TCE 
Keywords: Due window
Dynamic programming
Earliness-tardiness
Early-tardy jobs
Flowtime
Single-machine scheduling
Issue Date: 2000
Publisher: Pergamon Press
Source: Computers and operations research, 2000, v. 28, no. 2, p. 157-175 How to cite?
Journal: Computers and operations research 
Abstract: We study several single-machine non-preemptive scheduling problems to minimize the sum of weighted earliness-tardiness, weighted number of early and tardy jobs, common due window location, and flowtime penalties. We allow the due window location to be either a decision variable or a given parameter. We assume that the due window location has a tolerance and the window size is a given parameter. We further make the assumption that the ratios of the job processing times to the earliness-tardiness weights are agreeable for the first problem. We propose pseudo-polynomial dynamic programming algorithms to optimally solve the problems. We also provide polynomial time algorithms for several special cases. Scope and purpose The widespread use of Just-In-Time philosophy in manufacturing to eliminate inventories leads to a new class of scheduling problems in which the earliness and/or number of early jobs are penalized as well as the tardiness and/or tardy jobs. In this type of environments, the jobs are sometimes associated with a period of time within which they incur no penalty since the customers will generally allow a time interval for the delivery of the products. This time period is called a due window. There are a variety of applications with due windows in factory automation, production maintenance, and so on. In this paper, we consider the common due window problems to minimize the weighted earliness-tardiness, weighted number of early-tardy jobs and weighted flowtime on a single machine. The main contributions of this paper are identifying the computational complexity of the problems, developing dynamic programming algorithms to optimally solve them, and providing efficient and exact polynomial algorithms for the special cases.
URI: http://hdl.handle.net/10397/30725
ISSN: 0305-0548
EISSN: 1873-765X
DOI: 10.1016/S0305-0548(99)00097-0
Appears in Collections:Journal/Magazine Article

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

SCOPUSTM   
Citations

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

WEB OF SCIENCETM
Citations

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

Page view(s)

37
Last Week
3
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.