Dynamic Order Scheduling for Pick-and-pass System Considering Workload Balance and Learning Effects

doi:10.16182/j.issn1004731x.joss.24-0511

Abstract

Abstract:

In e-commerce logistics, the hybrid pick-and-pass systems offer both complexity and flexibility, enabling adaptation to a wider range of order picking scenarios. Therefore, they have been widely used. However, this also complicates the order scheduling problem, particularly when both workload balance and pickers' learning effects need to be considered. Efficiently scheduling orders to reduce picking time under these conditions poses a significant challenge. This study began by constructing a mathematical model for the static scheduling problem with known orders. Based on this model, a simulation model of hybrid pick-and-pass zones was developed, and a scheduling rule incorporating multiple system feature variables was proposed. The heuristic algorithm was employed to optimize the core parameters in the rules and achieve dynamic order scheduling. Simulation results based on real warehouse data demonstrate that the proposed method outperforms conventional scheduling rules and classical heuristic methods in both scheduling performance and computational efficiency, providing effective support for real-time decision-making in automated warehouse systems.

Key words: hybrid pick-and-pass system, dynamic order scheduling, order sequencing, workload balance, learning effect

CLC Number:

C935

Liu Weihong, Zhao Sixiang, Zhang Dali, Jiang Zhenhui. Dynamic Order Scheduling for Pick-and-pass System Considering Workload Balance and Learning Effects[J]. Journal of System Simulation, 2025, 37(10): 2613-2629.

Figures/Tables 14

Fig. 1

Fig. 2

Table 1

System characteristics of dynamic scheduling rules considering learning effects

指示	符号	系统特征	采集时间
订单 $i$	$n i$	订单 $i$ 待访问的分区数量	初始化阶段
	$m i, s$	订单 $i$ 在工序 $s$ 将访问的分区序号	初始化阶段
	$p i, m$	订单 $i$ 在待访问的分区 $m$ 中的拣选用时，对于熟练员工， $p i, m = p ¯ i, m$ ，对于新手员工， $p i, m = p i, m, t$ ，参考式(15)计算实际拣选时长	初始化阶段
分区 $m$	$δ m$	分区 $m$ 中员工水平处于熟练期则取1，处于学习期则取0	实时
	$N m$	当前时刻已到达分区 $m$ 的订单数量	实时
	$T m$	当前时刻已到达分区 $m$ 的订单拣选用时	实时
	$N p m$	对当前派发至系统中的所有订单，累计将在分区 $m$ 拣选的数量	实时
	$T p m$	对当前派发至系统中的所有订单，累计将在分区 $m$ 拣选的用时	实时
	$ω m$	分区 $m$ 拣选员累计拣选订单的数量， $ω m a x$ 指新手员工达到熟练期最少要拣选的订单数量	实时

Table 1

Table 2

Table 3

Scheduling rule design and codes

规则代号	规则描述	规则形式
N	考虑当前时刻已到达分区的订单数量， $X j = N j$	式 $(16)$
T	考虑当前时刻已到达分区的订单用时， $X j = T j$	式 $(16)$
Np	考虑当前系统即将到达该分区的累计订单数， $X j = N p j$	式 $(16)$
Tp	考虑当前系统即将到达该分区累计订单用时， $X j = T p j$	式 $(16)$
Np_HF	考虑当前系统内将到该分区的累计订单数量，增加新手员工熟练度对订单拣选用时的影响， $X j = N p j$	式 $(18)$
Tp_HF	考虑当前系统内将到该分区的累计订单用时，增加新手员工熟练度对订单拣选用时的影响， $X j = T p j$	式 $(18)$

Table 3

Table 4

Table 5

Table 6

Fig. 3

Table 7

Table 8

Fig. 4

Table 9

Table 10

References 41

[1]	颜伟, 孙佳旭, 崔若梁. 仓库拣选路径问题研究综述[J]. 科学技术与工程, 2022, 22(32): 14081-14089.
	Yan Wei, Sun Jiaxu, Cui Ruoliang. Review on Warehouse Picking Path Problem[J]. Science Technology and Engineering, 2022, 22(32): 14081-14089.
[2]	Jiang Min, Leung K H, Zhongyuan Lü, et al. Picking-replenishment Synchronization for Robotic Forward-reserve Warehouses[J]. Transportation Research Part E: Logistics and Transportation Review, 2020, 144: 102138.
[3]	Wu Wan, René B M de Koster, Yu Yugang. Forward-reserve Storage Strategies with Order Picking: When Do They Pay Off?[J]. IISE Transactions, 2020, 52(9): 961-976.
[4]	宋爽, 赵思翔, 张大力. 考虑并行分区的智能接力拣选系统储位分配问题研究[J]. 工业工程与管理, 2022, 27(5): 1-10.
	Song Shuang, Zhao Sixiang, Zhang Dali. A Storage Allocation Problem in an Intelligent Pick-and-pass System with Parallel Picking Zones[J]. Industrial Engineering and Management, 2022, 27(5): 1-10.
[5]	Garey M R, Johnson D S, Sethi R. The Complexity of Flowshop and Jobshop Scheduling[J]. Mathematics of Operations Research, 1976, 1(2): 117-129.
[6]	Jiang Xiaowei, Zhou Yaxian, Zhang Yuankai, et al. Order Batching and Sequencing Problem Under the Pick-and-sort Strategy in Online Supermarkets[J]. Procedia Computer Science, 2018, 126: 1985-1993.
[7]	纪佳溥. 自动化物流分拣系统智能调度的研究[D]. 北京: 机械科学研究总院, 2023.
	Ji Jiapu. Research on Intelligent Scheduling of Automatic Logistics Picking System[D]. Beijing: Mechanical Science Research Institute, 2023.
[8]	黄敏芳, 张源凯, 王颜新, 等. 基于JIT装配模式的网上超市订单分拣优化模型[J]. 中国管理科学, 2020, 28(5): 159-166.
	Huang Minfang, Zhang Yuankai, Wang Yanxin, et al. JIT Assembly Line-based Order Picking Process Optimization Method for Online Supermarkets[J]. Chinese Journal of Management Science, 2020, 28(5): 159-166.
[9]	Nawaz Muhammad, Enscore E E Jr, Ham I. A Heuristic Algorithm for the M-machine, N-job Flow-shop Sequencing Problem[J]. Omega, 1983, 11(1): 91-95.
[10]	安宇欣, 王转. 配送中心多区并行拣货系统投产顺序优化研究[J]. 计算机工程与应用, 2023, 59(7): 328-336.
	An Yuxin, Wang Zhuan. Research on Optimization of Production Sequence of Multi-district Parallel Picking System in Distribution Center[J]. Computer Engineering and Applications, 2023, 59(7): 328-336.
[11]	刘磊. 生产数据驱动的动态作业车间调度规则决策研究[D]. 重庆: 重庆邮电大学, 2019.
	Liu Lei. The Research of Scheduling Rules Decision-making Based on Production Data of Dynamic Job Shop[D]. Chongqing: Chongqing University of Posts and Telecommunications, 2019.
[12]	范华丽, 熊禾根, 蒋国璋, 等. 动态车间作业调度问题中调度规则算法研究综述[J]. 计算机应用研究, 2016, 33(3): 648-653.
	Fan Huali, Xiong Hegen, Jiang Guozhang, et al. Survey of Dispatching Rules for Dynamic Job-shop Scheduling Problem[J]. Application Research of Computers, 2016, 33(3): 648-653.
[13]	Nguyen S, Mei Yi, Xue Bing, et al. A Hybrid Genetic Programming Algorithm for Automated Design of Dispatching Rules[J]. Evolutionary Computation, 2019, 27(3): 467-496.
[14]	Vlašić Ivan, Ðurasević Marko, Jakobović Domagoj. Improving Genetic Algorithm Performance by Population Initialisation with Dispatching Rules[J]. Computers & Industrial Engineering, 2019, 137: 106030.
[15]	Aytug H, Lawley M A, McKay K, et al. Executing Production Schedules in the Face of Uncertainties: A Review and Some Future Directions[J]. European Journal of Operational Research, 2005, 161(1): 86-110.
[16]	Holthaus Oliver, Rajendran Chandrasekharan. Efficient Jobshop Dispatching Rules: Further Developments[J]. Production Planning & Control, 2000, 11(2): 171-178.
[17]	李豆豆. 生产调度的启发式规则研究综述[J]. 机械设计与制造工程, 2014, 43(2): 51-56.
	Li Doudou. An Overview on Heuristic Rules for the Production Scheduling Problem[J]. Machine Design and Manufacturing Engineering, 2014, 43(2): 51-56.
[18]	Rajendran Chandrasekharan, Holthaus Oliver. A Comparative Study of Dispatching Rules in Dynamic Flowshops and Jobshops[J]. European Journal of Operational Research, 1999, 116(1): 156-170.
[19]	Branke Jürgen, Nguyen S, Pickardt C W, et al. Automated Design of Production Scheduling Heuristics: A Review[J]. IEEE Transactions on Evolutionary Computation, 2016, 20(1): 110-124.
[20]	Priore Paolo, Gómez Alberto, Pino Raúl, et al. Dynamic Scheduling of Manufacturing Systems Using Machine Learning: An Updated Review[J]. Artificial Intelligence for Engineering Design, Analysis and Manufacturing, 2014, 28(1): 83-97.
[21]	Branke Jürgen, Hildebrandt Torsten, Scholz-Reiter Bernd. Hyper-heuristic Evolution of Dispatching Rules: A Comparison of Rule Representations[J]. Evolutionary Computation, 2015, 23(2): 249-277.
[22]	źUrasević Marko, Jakobović Domagoj. Evolving Dispatching Rules for Optimising Many-objective Criteria in the Unrelated Machines Environment[J]. Genetic Programming and Evolvable Machines, 2018, 19(1/2): 9-51.
[23]	Oukil Amar, El-Bouri Ahmed. Ranking Dispatching Rules in Multi-objective Dynamic Flow Shop Scheduling: A Multi-faceted Perspective[J]. International Journal of Production Research, 2021, 59(2): 388-411.
[24]	Zhou Yong, Yang Jianjun. Automatic Design of Scheduling Policies for Dynamic Flexible Job Shop Scheduling by Multi-objective Genetic Programming Based Hyper-heuristic[J]. Procedia CIRP, 2019, 79: 439-444.
[25]	陈亚绒, 管舒晨, 黄成军, 等. 基于仿真的双目标并行机开放车间自适应动态调度[J]. 系统仿真学报, 2023, 35(1): 69-81.
	Chen Yarong, Guan Shuchen, Huang Chengjun, et al. Simulation-Based Adaptive Dynamic Scheduling for Bi-objective Parallel Multi-processor Open Shop[J]. Journal of System Simulation, 2023, 35(1): 69-81.
[26]	Liu Weibo, Jin Yan, Price M. New Scheduling Algorithms and Digital tool for Dynamic Permutation Flowshop with Newly Arrived Order[J]. International Journal of Production Research, 2017, 55(11): 3234-3248.
[27]	Shahrabi Jamal, Mohammad Amin Adibi, Mahootchi Masoud. A Reinforcement Learning Approach to Parameter Estimation in Dynamic Job Shop Scheduling[J]. Computers & Industrial Engineering, 2017, 110: 75-82.
[28]	Chen Jian, Wang Meilin, Kong Xiang, et al. Manufacturing Synchronization in a Hybrid Flowshop with Dynamic Order Arrivals[J]. Journal of Intelligent Manufacturing, 2019, 30(7): 2659-2668.
[29]	Liu Weibo, Jin Yan, Price M. New Meta-heuristic for Dynamic Scheduling in Permutation Flowshop with New Order Arrival[J]. The International Journal of Advanced Manufacturing Technology, 2018, 98(5): 1817-1830.
[30]	Rahman H F, Janardhanan M N, Izabela Ewa Nielsen. Real-time Order Acceptance and Scheduling Problems in a Flow Shop Environment Using Hybrid GA-PSO Algorithm[J]. IEEE Access, 2019, 7: 112742-112755.
[31]	Wang Jinzhi, Qu Shuhui, Wang Jie, et al. Real-time Decision Support with Reinforcement Learning for Dynamic Flowshop Scheduling[C]//Smart SysTech 2017; European Conference on Smart Objects, Systems and Technologies. Piscataway: IEEE, 2017: 1-9.
[32]	Mohamed Habib Zahmani, Atmani Baghdad. Multiple Dispatching Rules Allocation in Real Time Using Data Mining, Genetic Algorithms, and Simulation[J]. Journal of Scheduling, 2021, 24(2): 175-196.
[33]	Yang Shengluo, Xu Zhigang, Wang Junyi. Intelligent Decision-making of Scheduling for Dynamic Permutation Flowshop via Deep Reinforcement Learning[J]. Sensors, 2021, 21(3): 1019.
[34]	Yang Shengluo, Wang Junyi, Xu Zhigang. Real-time Scheduling for Distributed Permutation Flowshops with Dynamic Job Arrivals Using Deep Reinforcement Learning[J]. Advanced Engineering Informatics, 2022, 54: 101776.
[35]	Zeiträg Yannik, José Rui Figueira, Horta Nuno, et al. Surrogate-assisted Automatic Evolving of Dispatching Rules for Multi-objective Dynamic Job Shop Scheduling Using Genetic Programming[J]. Expert Systems with Applications, 2022, 209: 118194.
[36]	Wright T P. Factors Affecting the Cost of Airplanes[J]. Journal of the Aeronautical Sciences, 1936, 3(4): 122-128.
[37]	Biskup Dirk. Single-machine Scheduling with Learning Considerations[J]. European Journal of Operational Research, 1999, 115(1): 173-178.
[38]	Marichelvam M K, Geetha M, Tosun Ömür. An Improved Particle Swarm Optimization Algorithm to Solve Hybrid Flowshop Scheduling Problems with the Effect of Human Factors-a Case Study[J]. Computers & Operations Research, 2020, 114: 104812.
[39]	Lu Yuanyuan, Wang Jibo. Some Single-machine Scheduling with Sum-of-processing-time-based and Job-position-based Processing Times[J]. Applied Mathematical Modelling, 2013, 37(10/11): 6695-6702.
[40]	Wu C C, Wang Dujuan, Cheng S R, et al. A Two-stage Three-machine Assembly Scheduling Problem with a Position-based Learning Effect[J]. International Journal of Production Research, 2018, 56(9): 3064-3079.
[41]	De Jong J R. The Effects of Increasing Skill on Cycle Time and Its Consequences for Time Standards[J]. Ergonomics, 1957, 1(1): 51-60.

分区序号	工作量(单位时间)
I	8 742
II	14 135
III	9 799
IV	8 472
V	6 988
VI	12 756

规则代号	参数优化结果	迭代次数	迭代用时/s
N	[0.61, 0.18, 0.04, 1.00, 0.58, 0.11]	20	4 000
T	[0.92, 0.29, 0, 0.98, 0.72, 0]	22	4 309
Np	[0.19, 0.15, 0.15, 0.40, 0.41, 0.33]	22	4 309
Tp	[0.22, 0.50, 0.12, 0, 0.99, 0.20]	25	4 925
Np_HF	[0.22, 0.41, 0.08, -0.11, -0.48, -0.08, 0.25, 0.12, 0.43, 0.50, 0.31, 0.35]	29	5 909
Tp_HF	[0.03, 0.32, 0.15, -0.06, -0.50, -0.26, 0.40, 0.08, 0.42, 0.24, -0.27, 0.43]	23	3 189

规则名称	规则代号	规则描述
先到先发规则	FCFS	直接将拣选订单按照其到达的时间顺序派发，当流水线的主路出现堵塞时就停止对经过该段路径订单的派发
最短加工时间规则	SPT	在每个派单时刻，从所有不受到堵塞问题影响的、可派发的订单中选择总加工时长最短的订单进行派发
最长加工时间规则	LPT	在每个派单时刻，从所有不受到堵塞问题影响的、可派发的订单中选择总加工时长最长的订单进行派发
随机排序规则	RAND	将待派发订单进行随机排列，按照排列顺序依次派发，同样对出现拥堵问题的订单暂停该时刻的派发
NEH启发式规则	NEH	一种解决经典静态流水车间问题的常用规则，将待调度订单按总加工时间的非增顺序进行排序，再依次按顺序选择订单重新排列，将其插入到对总工作时间增加最少的位置

类别	调度规则代号	工作总用时(单位时间)	与FCFS用时对比/%	工作平衡性	与FCFS的平衡性对比/%
对比规则	FCFS	15 623		0.18
	SPT	16 074	2.9	0.17	-7.2
	LPT	15 840	1.4	0.16	-13.8
	RAND	15 146	-3.1	0.18	-3.0
	NEH	15 035	-3.8	0.18	-0.6
本文规则	N	14 307	-8.4	0.13	-29.3
	T	14 244	-8.8	0.13	-29.4
	Np	14 146	-9.5	0.13	-30.4
	Tp	14 136	-9.5	0.11	-39.0

类别	调度规则代号	工作总用时(单位时间)	与FCFS用时对比/%	工作平衡性	与FCFS平衡性对比/%
对比规则	FCFS	17 367		0.19
	SPT	17 590	1.3	0.18	-6.2
	LPT	17 521	0.9	0.16	-15.0
	RAND	16 992	-2.2	0.19	-1.4
本文规则	Np	16 475	-5.1	0.13	-28.2
	Tp	16 404	-5.5	0.12	-35.5
	Np_HF	14 310	-17.6	0.12	-37.1
	Tp_HF	14 242	-18.0	0.12	-38.7