Title :
Minimizing Number of Tardy Jobs on a Batch Processing Machine with Incompatible Job Families
Author :
Liu, Lili ; Zhang, Feng
Author_Institution :
Sch. of Sci., Shanghai Second Polytech. Univ., Shanghai
Abstract :
In this paper we prove that the problem of scheduling jobs with incompatible job families on a single batch processing machine to minimize number of tardy jobs is strongly (unary) NP-hard. We then develop a dynamic programming algorithm for minimizing weighted number of tardy jobs on a single batch processing machine with incompatible job families.
Keywords :
batch processing (industrial); computational complexity; dynamic programming; job shop scheduling; production equipment; NP-hard problem; dynamic programming algorithm; incompatible job families; single batch processing machine; tardy jobs; Circuit testing; Communication system control; Dynamic programming; Heuristic algorithms; Integrated circuit manufacture; Integrated circuit testing; Job shop scheduling; Polynomials; Processor scheduling; Very large scale integration; Batch processing; Incompatible; Np-hard;
Conference_Titel :
Computing, Communication, Control, and Management, 2008. CCCM '08. ISECS International Colloquium on
Conference_Location :
Guangzhou
Print_ISBN :
978-0-7695-3290-5
DOI :
10.1109/CCCM.2008.107
