Title :
Scheduling jobs on parallel batch processing machines
Author :
Liu, Lili ; Wang, Jibo ; Zhang, Feng
Author_Institution :
Sch. of Sci., Shanghai Second Polytech. Univ., Shanghai, China
Abstract :
In this paper we consider the problem of scheduling jobs with and without release dates on parallel unbounded batch processing machines to minimize total completion time. We show that the problem with release dates is strongly NP-hard by a reduction from the strongly NP-hard 3-Partition problem and develop a dynamic programming algorithm for the problem without release dates.
Keywords :
batch processing (industrial); computational complexity; dynamic programming; scheduling; dynamic programming algorithm; job scheduling; parallel unbounded batch processing machines; release dates; strongly NP-hard 3-partition problem; total completion time; Aerospace engineering; Communication system control; Concurrent computing; Dynamic programming; Engineering management; Heuristic algorithms; Job shop scheduling; Manufacturing industries; Processor scheduling; Telephony; batch processing machine; release date; 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.5268145
