Scheduling unrelated parallel batch processing machines with non-identical job sizes

作者：Li, XiaoLin; Huang, YanLi^*; Tan, Qi; Chen, HuaPing

来源：Computers & Operations Research, 2013, 40(12): 2983-2990.

DOI：10.1016/j.cor.2013.06.016

• Scheduling
• Unrelated parallel batch processing machines
• Makespan
• Heuristics

Scheduling unrelated parallel batch processing machines to minimize makespan is studied in this paper. Jobs with non-identical sizes are scheduled on batch processing machines that can process several jobs as a batch as long as the machine capacity is not violated. Several heuristics based on best fit longest processing time (BFLPT) in two groups are proposed to solve the problem. A lower bound is also proved to evaluate the quality of the heuristics. Computational experiments were undertaken. These showed that J_SC-BFLPT, considering both load balance of machines and job processing times, was robust and outperformed other heuristics for most of the problem categories.

• 出版日期2013-12
• 单位中国科学技术大学; 中国矿业大学（北京）; 合肥工业大学