SCHEDULING A SINGLE BATCH PROCESSING MACHINE WITH NONIDENTICAL JOB SIZES

被引：367
作者：
UZSOY, R
机构：
[1] School of Industrial Engineering, Purdue University, West Lafayette, IN, 47907-1287
来源：
INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH | 1994年 / 32卷 / 07期
基金：
美国国家科学基金会;
关键词：
D O I：
10.1080/00207549408957026
中图分类号：
T [工业技术];
学科分类号：
08 ;
摘要：
The problem of scheduling jobs with non-identical capacity requirements or sizes on a single batch processing machine to minimize total completion time and makespan is studied. These problems are proven to be NP-hard and heuristics are developed for both, as well as a branch and bound algorithm for the total completion time problem. Computational experiments show that the heuristics are capable of rapidly obtaining near-optimal solutions.
引用
收藏
页码：1615 / 1635
页数：21
相关论文
共 16 条
[1]  
Ahmadi J.H., Ahmadi R.H., Dasu S., Tang C.S., Batching and scheduling jobs on batch and discrete processors, Operations Research, 40, pp. 750-763, (1992)
[2]  
Bruno J., Coffman E.G., Sethi R., Scheduling independent tasks to reduce mean finishing time, Communications of the ACM, 17, pp. 382-387, (1974)
[3]  
Chandra P., Gupta S., An Analysis of a Last-Station-Bottlcneck Semiconductor Packaging Line, (1992)
[4]  
Chandru V., Lee C.Y., Uzsoy R., Minimizing total completion time on batch processing machines, International Journal of Production Research, 31, pp. 2097-2121, (1993)
[5]  
Chandru V., Lee C.Y., Uzsoy R., Minimizing total completion time on a batch processing machine with job families, Operations Research Letters, 13, pp. 61-65, (1993)
[6]  
Coffman E.G., Garey M.R., Johnson D.S., Approximation algorithms for bin- packing-an updated survey, Algorithm Design for Computer System Design, pp. 49-106, (1984)
[7]  
Dobson G., Nambinadom R.S., The Batch Loading and Scheduling Problem, (1992)
[8]  
Eastman W.L., Even S., Isaacs I.M., Bounds for the optimal scheduling of n jobs on m processors, Management Science, 11, pp. 268-279, (1964)
[9]  
Fowler J.W., Hogg G.L., Phillips D.T., Control of multiproduct bulk server diffusion/oxidation processes, IIE Transactions on Scheduling and Logistics, 24, pp. 84-96, (1992)
[10]  
French S., Sequencing and Scheduling: An Introduction to the Mathematics of the Job-Shop, (1982)
12