极小化总完工时间的单机连续型批调度问题

Scheduling a Single Continuous Batch Processing Machine to Minimize Total Completion Time

连续型批处理机调度问题是一种新型的批调度问题,它是从钢铁工业加热炉对管坯的加热过程中提炼出来的.批的加工时间取决于该批的大小、批中工件的最大加工时间及机器的容量.本文研究了目标函数是极小化总完工时间问题,对最优解的性质进行了理论分析,提出了最优的分批策略及批间序的确定方法,给出了一个多项式可解的动态规划算法.

This paper addresses a problem of continuous batch scheduling arising in the heating-process of blooms in steel industry. Each heating furnace is modeled as continuous batch processing machine, which can handle more than one job simultaneously. The processing time of a batch depends on its size, the longest processing time of jobs in the batch and the capacity of the batching machine. In this paper we consider the problem for minimizing total completion time. The theoretic analysis of optimal solution properties are given,and the optimal policy of hatching and the method of sequencing the batches are provided. A dynamic programming algorithm with a polynomial running time is represented based on the properties of batching and scheduling.