Research Article

Online scheduling model of batch processing machine considering order types and setup time

  • Kaiyuan JIN ,
  • Feifeng ZHENG ,
  • Ming LIU
Expand
  • 1. School of Management Science and Information Engineering, Hebei University of Economics and Business, Shijiazhuang 050062, Hebei, China
    2. Glorious Sun School of Business and Management, Donghua University, Shanghai 200051, China
    3. School of Economics and Management, Tongji University, Shanghai 200092, China

Received date: 2022-11-20

  Online published: 2025-12-11

Copyright

, 2025, All rights reserved. Unauthorized reproduction is prohibited.

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.

Cite this article

Kaiyuan JIN , Feifeng ZHENG , Ming LIU . Online scheduling model of batch processing machine considering order types and setup time[J]. Operations Research Transactions, 2025 , 29(4) : 231 -240 . DOI: 10.15960/j.cnki.issn.1007-6093.2025.04.018

References

1 Hur Y , Bard J F , Chacon R . Hierarchy machine set-up for multi-pass lot scheduling at semiconductor assembly and test facilities[J]. International Journal of Production Research, 2019, 57 (14): 4351- 4370.
2 Wu W , Hayashi T , Haruyasu K , et al. Exact algorithms based on a constrained shortest path model for robust serial-batch and parallel-batch scheduling problems[J]. European Journal of Operational Research, 2023, 307 (1): 82- 102.
3 唐国春, 井彩霞. 现代排序论应用[J]. 自然杂志, 2015, 37 (2): 115- 120.
4 Toksari M D , Toga G . Single batch processing machine scheduling with sequence-dependent setup times and multi-material parts in additive manufacturing[J]. CIRP Journal of Manufacturing Science and Technology, 2022, 37, 302- 311.
5 Lu S J , Kong M , Zhou Z P , et al. A hybrid metaheuristic for a semiconductor production scheduling problem with deterioration effect and resource constraints[J]. Operational Research, 2022, 22 (5): 5405- 5440.
6 Shahidi-Zadeh B , Tavakkoli-Moghaddam R , Taheri-Moghadam A , et al. Solving a bi-objective unrelated parallel batch processing machines scheduling problem: A comparison study[J]. Computers & Operations Research, 2017, 88, 71- 90.
7 He C , Lin H , Li L . Hierarchical minimization of two maximum costs on a bounded serial-batching machine[J]. RAIRO-Operations Research, 2021, 55 (1): 135- 140.
8 Yin Y Q , Li D D , Wang D J , et al. Single-machine serial-batch delivery scheduling with two competing agents and due date assignment[J]. Annals of Operations Research, 2021, 298 (1-2): 497- 523.
9 Gahm C , Wahl S , Tuma A . Scheduling parallel serial-batch processing machines with incompatible job families, sequence-dependent setup times and arbitrary sizes[J]. International Journal of Production Research, 2022, 60 (17): 5131- 5154.
10 Shahvari O , Logendran R . An enhanced tabu search algorithm to minimize a bi-criteria objective in batching and scheduling problems on unrelated-parallel machines with desired lower bounds on batch sizes[J]. Computers & Operations Research, 2017, 77, 154- 176.
11 Pei J , Song Q R , Liao B Y , et al. Parallel-machine serial-batching scheduling with release times under the effects of position-dependent learning and time-dependent deterioration[J]. Annals of Operations Research, 2021, 298 (1-2): 407- 444.
12 He C , Li S S , Wu J . Simultaneous optimization scheduling with two agents on an unbounded serial-batching machine[J]. RAIRO-Operations Research, 2021, 55 (6): 3701- 3714.
13 Borodin A , El-Yaniv R . Online Computation and Competitive Analysis[M]. Cambridge: Cambridge University Press, 2005.
14 Fiat A , Woeginger G J . Online Algorithms: The State of the Art[M]. Berlin: Springer, 1998.
Outlines

/