批量无限时极小化工件配送时间的单机在线算法

On-line scheduling on a batch processing machine with unbounded batch size to minimize the delivery time

研究的问题包括两个阶段,第一阶段为工件的加工阶段.工件要在一台批处理机上加工,最多可以B个组成一批,批的加工时间为该批中加工时间最长的工件的加工时间,加工过程中不允许被打断.第二阶段为工件的运输阶段,即完工的工件要运往目的地,由于工件的不同,运往目的地所需要的时间也不同.所谓的配送时间是指工件的完工时间和运输时间的总和,目的是使工件的最大配送时间最小.

The problem contains two stage, in which jobs are processed by one first stage processor. The batehing machine can process up tojobs simutaneously, the processing time of a batch is a maximum processing time among all jobs in it. Preemption is not allowed. In the second stage, the completed jobs need to be delivered to the destination. Our objective is to minimize the delivery time, which is the sum of the job comletion and transportation time. For this problem we propose three on -line algorithms that are best possible for some special problems.