A PTAS for Common Due Window Scheduling with Window Penalty on Identical Machines
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.
scheduling identicalmachines duewindow early tardy
Hongluan Zhao Hongwei Ma Guoyong Han Linsheng Zhao
Department of Computer Science and Technology, Shandong Jianzhu University, Jinan, China
国际会议
太原
英文
648-652
2010-10-22（万方平台首次上网日期，不代表论文的发表时间）