Title :
A heuristic for optimal job scheduling problem with a common due window on parallel and identical machines
Author :
Decai, Huang ; Yanwei, Zhao ; Yihua, Zhu
Author_Institution :
Res. Center of Sci., Zhejiang Univ. of Technol., China
Abstract :
The paper is concerned with the job scheduling problem with a common due window. After giving an optimal algorithm for the single machine problem, a mathematical model for the similar problem on parallel and identical machines is presented. Because the job scheduling problem on parallel and identical machines, which may be NP-complete, is much more complex than that on a single machine, a heuristic algorithm is given to find an approximate solution after two important theorems are proved. The numerical example illustrates that the heuristic algorithm is very effective in obtaining a near-optimal solution
Keywords :
computational complexity; minimisation; production control; NP-complete problem; common due window; identical machines; near-optimal solution; optimal algorithm; optimal job scheduling problem; parallel machines; Heuristic algorithms; Job shop scheduling; Manufacturing systems; Mathematical model; NP-complete problem; Processor scheduling; Research and development management; Scheduling algorithm; Single machine scheduling; Technology management;
Conference_Titel :
Intelligent Control and Automation, 2000. Proceedings of the 3rd World Congress on
Conference_Location :
Hefei
Print_ISBN :
0-7803-5995-X
DOI :
10.1109/WCICA.2000.862910
