English

运筹学学报（中英文） ›› 2025, Vol. 29 ›› Issue (4): 231-240.doi: 10.15960/j.cnki.issn.1007-6093.2025.04.018

• • 上一篇    

考虑订单类型和准备时间的批处理机在线调度模型研究

靳凯媛1,†, 郑斐峰2, 刘明3   

  1. 1. 河北经贸大学管理科学与信息工程学院, 河北石家庄 050062;
    2. 东华大学旭日工商管理学院, 上海 200051;
    3. 同济大学经济与管理学院, 上海 200092
  • 收稿日期:2022-11-20 发布日期:2025-12-11
  • 通讯作者: 靳凯媛 E-mail:jinkaiyuan@hueb.edu.cn
  • 基金资助:
    国家自然科学基金(Nos.71832001,72271051,72071144),中央高校基本科研专项资金(No.2232018H-07),河北省教育厅科学研究项目资助(No.BJ2025193),东华大学研究生创新基金(No.CUSF-DH-D-2021067)

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

JIN Kaiyuan1,†, ZHENG Feifeng2, LIU Ming3   

  1. 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:2022-11-20 Published:2025-12-11

PDF

2

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

关键词: 在线调度, 批处理机, 在线算法, 竞争比

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

中图分类号: