Please use this identifier to cite or link to this item:
Title: Single-machine scheduling with a common due window
Authors: Yeung, WK
Oguz, C
Cheng, TCE 
Keywords: Due window
Dynamic programming
Early-tardy jobs
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.
ISSN: 0305-0548
EISSN: 1873-765X
DOI: 10.1016/S0305-0548(99)00097-0
Appears in Collections:Journal/Magazine Article

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


Last Week
Last month
Citations as of Nov 7, 2018


Last Week
Last month
Citations as of Nov 14, 2018

Page view(s)

Last Week
Last month
Citations as of Nov 12, 2018

Google ScholarTM



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