Scheduling algorithms for heterogeneous batch processors with incompatible job-families |
| |
Authors: | M Mathirajan A I Sivakumar V Chandru |
| |
Affiliation: | (1) Singapore-MIT Alliance, School of MPE, NTU, Singapore, 639 798;(2) Department of Computer Science and Automation, IISc, Bangalore, 560 012, India |
| |
Abstract: | We consider the problem of scheduling heterogeneous batch processors (i.e., batch processors with different capacity) with incompatible job-families and non-identical job sizes to maximize the utilization of the batch processors. We analyzed the computational complexity of this problem and showed that it is NP-hard and proposed eight variants of a fast greedy heuristic. A series of computational experiments were carried out to compare the performance of the heuristics and showed that the heuristics are capable of consistently obtaining near (estimated) optimal solutions with very low-computational burden for large-scale problems. We also carried out a study to find the effect of family processing time changes on the performance of the heuristics. This sensitivity analysis indicated that the processing time set of job-families influences the performance of the heuristic algorithms. |
| |
Keywords: | Heterogeneous batch processors incompatible job-families non-identical job-sizes heuristics scheduling |
本文献已被 SpringerLink 等数据库收录! |
|