本文探讨了批容量有限的一类批处理机在线调度问题。在订单实时释放的场景下, 针对订单具有不同类型、同类型订单才能组批、不同类型订单批次之间需要既定准备时间、批处理时长依赖于订单类型的调度模型, 以最大化总完工收益为优化目标, 着重考察了两种加工情形。对于单台批处理机的在线模型, 证明了问题的竞争比下界为$ 1+w$, 其中$ w$表示批次的最大完工收益。同时, 设计了考虑准备时间的在线算法, 并运用最坏情形分析法证明了其竞争比等于下界, 表明该算法具有最优竞争性。对于两台平行批处理机的情形, 提出了一个竞争比为$ 1+2\sqrt{w}$的在线算法。

In order to improve the utilization of resources and shorten the delivery time of customer orders, this paper discusses the online scheduling problem of batch processing machine with limited batch capacity. In the scenario of on-time release time of orders, an online scheduling model with different types of orders, only orders of the same type that can be grouped into batches and the processing time of batch which depends on the type of order is studied. Besides, if two consecutive batches belong to different types, there is a fixed setup time between them. Taking the total revenue as the optimization objective, two processing cases are investigated. As for the online model of a single batch processing machine, the lower bound of the problem is proved to be $ 1+w$, in which $ w$ is the largest revenue of a batch. At the same time, an online algorithm which considers setup time is designed, and the competitive ratio of the online algorithm proved by the Worst Case Analysis method is equal to the lower bound, which shows that the algorithm has the optimal competition. For the case of two parallel batch processing machines, an online algorithm with competitive ratio of $ 1+2\sqrt{w}$ is proposed. The results of the paper can be used to guide the design of efficient online scheduling scheme in practice.