Title :
Linear programming relaxation algorithm for scheduling problem with controllable processing times
Author :
Zhang, Feng ; Liu, Lili
Author_Institution :
Sch. of Sci., Shanghai Second Polytech. Univ., Shanghai, China
Abstract :
In this paper we provide a linear programming relaxation algorithm for scheduling problem with controllable processing times. This problem is NP-hard even if there are no precedence constraints between the jobs. We prove that the performance ratio of the algorithm is 4.
Keywords :
computational complexity; job shop scheduling; linear programming; NP-hard problem; controllable processing time; job scheduling; linear programming relaxation algorithm; scheduling problem; Chemical processes; Communication system control; Costs; Electronic mail; Linear programming; Process control; Processor scheduling; Scheduling algorithm; Single machine scheduling; controllable processing time; linear programming; scheduling;
Conference_Titel :
Computing, Communication, Control, and Management, 2009. CCCM 2009. ISECS International Colloquium on
Conference_Location :
Sanya
Print_ISBN :
978-1-4244-4247-8
DOI :
10.1109/CCCM.2009.5268146
