DocumentCode
2857839
Title
A PTAS for common due window scheduling with window penalty on identical machines
Author
Zhao, Linsheng ; Ma, Hongwei ; Han, Guoyong ; Linsheng Zhao
Author_Institution
Dept. of Comput. Sci. & Technol., Shandong Jianzhu Univ., Jinan, China
Volume
10
fYear
2010
fDate
22-24 Oct. 2010
Abstract
We study the problem with a set of independent jobs to be processed on some identical parallel machines. Jobs should be completed as close as possible to the common due window, but the window location is a decision variable with linear penalty. The objective is to find a schedule to minimize the sum of earliness and tardiness penalties together with window location cost. Since it is strongly NP-complete, polynomial time approximation schemes are firstly proposed.
Keywords
optimisation; parallel machines; polynomial approximation; single machine scheduling; NT-complete; PTAS; linear penalty; machine scheduling; parallel machines; polynomial time approximation schemes; window location cost; window penalty; window scheduling; Electronic mail; Schedules; Silicon; due window; early; identical machines; scheduling; tardy;
fLanguage
English
Publisher
ieee
Conference_Titel
Computer Application and System Modeling (ICCASM), 2010 International Conference on
Conference_Location
Taiyuan
Print_ISBN
978-1-4244-7235-2
Electronic_ISBN
978-1-4244-7237-6
Type
conf
DOI
10.1109/ICCASM.2010.5622230
Filename
5622230
Link To Document