Abstract:

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.

Key words: online scheduling, batch processing machine, online algorithm, competitive ratio