Bayesian dynamic scheduling of multipurpose batch processes under incomplete look-ahead information

Taicheng Zheng; Dan Li; Jie Li

cs.LGNov 30, 2025

Bayesian dynamic scheduling of multipurpose batch processes under incomplete look-ahead information

Authors: Taicheng Zheng, Dan Li, Jie Li

Organizations: Centre for Process Integration, the Department of Chemical Engineering, The University of Manchester, Oxford Road, Manchester, M13 9SS, United Kingdom

Abstract

Multipurpose batch processes become increasingly popular in manufacturing industries since they adapt to low-volume, high-value products and shifting demands. These processes often operate in a dynamic environment, which faces disturbances such as processing delays and demand changes. To minimise long-term cost and system nervousness (i.e., disruptive changes to schedules), schedulers must design rescheduling strategies to address such disturbances effectively. Existing methods often assume complete look-ahead information over the scheduling horizon. This assumption contrasts with realistic situations where schedulers can only access incomplete look-ahead information. Sticking with existing methods may lead to suboptimal long-term costs and high-level system nervousness. In this work we propose a Bayesian dynamic scheduling method. Our method relies on learning a Bayesian Network from the probability distribution of disturbances. Specifically, the Bayesian Network represents how likely each operation will be impacted by disturbances. During the online execution, when new disturbances become observed, this method updates the posterior distribution and therefore guides the rescheduling strategy. We compare our method with the existing periodic rescheduling strategy (which generates new schedules from scratch at fixed intervals) on four benchmark problems. Computational results show that our method achieves statistically better long-term costs and system nervousness. In the theoretical aspect, we prove that if disturbances are mutually independent, the impact-quantifying variables inherently satisfy the independence assumptions required by Bayesian Networks. As an implication, practitioners can extend the method to other scheduling problems (such as job shop scheduling and continuous processes), given that they define the problem-specific dependencies between operations.

Figures & tables

Figure 1: STN representation of a sample multipurpose batch process.

Figure 2: Illustration of look-ahead information and action sequences.

Figure 3: Flowchart of the overall procedure of the Bayesian dynamic scheduling method. BN: BN ; EU: evidentially unrecoverable; PU: probabilistically unrecoverable.

Figure 4: STN of the illustrative example.

Figure 5: Planned schedule of the illustrative example. The label inside each bar shows the task name and the batch size. The operation index is annotated above the bar. The idle gap of one time period on machine

j_{3}

between

\mathcal{O}_{5}

and

\mathcal{O}_{6}

is induced by the material-availability constraint, since

\mathcal{O}_{6}

cannot start before

\mathcal{O}_{3}

completes at

t_{4}

Figure 6: BN over the impact variables of the illustrative example. The shaded node $Z_{\mathcal{O}_{1}}$ represents the observation at $t=1$ . Posterior marginals $\hat{\mathsf{P}}(Z_{\mathcal{O}_{i}}=1\mid Z_{\mathcal{O}_{1}}=1)$ obtained via inference algorithms are shown next to each unobserved node.

Figure 7: Illustration of the ImpactPropagation algorithm.

	$n$	$\gamma_{2}$	$\gamma_{3}$
Example 1	1000	0.5	0.5
Example 2	1000	0.5	0.5
Example 3	2500	0.5	0.5
Example 4	4000	0.4	0.6

Table 1: Main algorithm parameters

Figure 8: Compilation of computational results. In each subplot, the x-axis represents costs (the value of

c

). The y-axis represents the number of operation changes (the value of

d

). The light blue vertical line represents the value of

c^{*}

. The pink vertical line represents the value of

c^{\infty}

. Each light brown scatter represents a result that is generated by the periodic, completely rescheduling policy. The integer to the top right of a light brown scatter represents the corresponding rescheduling frequency, which is measured in hours. Each light green scatter represents a result that is generated by our Bayesian dynamic scheduling method.

Figure 9: Stack plots of computational times generated by the periodically rescheduling policy with a rescheduling frequency of every hour (left) and our Bayesian dynamic scheduling method (right)

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 10: Decision tree for determining the value of state variable

r_{i,j,t+1}

. In this decision tree, each non-leaf node denotes a system variable from the previous time step that may influence the value of

r_{i,j,t+1}

. Each arc outgoing from a non-leaf node represents a set of possible values for the corresponding non-leaf node variable. Each leaf node represents a set of possible values that the state variable

r_{i,j,t+1}

can take, determined by travelling the decision tree from the root node to the leaf node.

Figure 11: Illustration of different operation statuses corresponding to the leaf nodes of the decision tree shown in Figure 10

Figure 12: Illustration of the propagation function for processing time variations

Decision-Making under Uncertainty

Decision-making under uncertainty studies how to choose actions when outcomes, states, or models are imperfectly known.

See all 201 papers

Planning and Scheduling Business Processes under Control-Flow Uncertainty: Extended Version
Sep 4, 2026Michel Kunkler, Stefanie Rinderle-MaStochastic Optimization Chance-Constrained Optimization
Technical University of Munich, Germany TUM School of Computation, Information, and Technology
DSevolve: Enabling Real-Time Adaptive Scheduling on Dynamic Flexible Job Shop with LLM-Evolved Heuristic Portfolios
Mar 29, 2026XinLei Zhou, Jin Huang, Jie Yang +2Flexible Job Shop Scheduling Real-Time Scheduling
School of Mechanical Science and Engineering, Huazhong University of Science and Technology, Wuhan, 430074, PR China
DynaSchedBench: Calibrated Dynamic Scheduling Benchmarks and Observability Paradox in LLM-based Scheduling Agents
May 26, 2026Shijie Cao, Yuan Yuan, Jing LiuLLM Agent Evaluation Combinatorial Optimization
School of Computer Science and Engineering, Beihang University, Beijing 100191, China · Shenzhen Loop Area Institute, Shenzhen, China · Qingdao Research Institute, Beihang University +3

Sep 4, 2026J/K move · Enter open · S save

Planning and Scheduling Business Processes under Control-Flow Uncertainty: Extended Version

Michel Kunkler, Stefanie Rinderle-Ma

Technical University of Munich, Germany TUM School of Computation, Information, and Technology

Stochastic Optimization Chance-Constrained Optimization Business Process Automation Decision-Making under Uncertainty Operations Research

Open paper AskPDF arXiv

Scheduling activities in business processes can improve efficiency (e.g., reduce makespan), but is challenging because the exact sequence of activities required to complete a case is often uncertain due to decisions based on data that emerges during execution. Nevertheless, probabilistic information regarding such decisions can often be estimated or derived from historical execution logs, and can help anticipate which execution paths are likely to lead to successful completion. Planning with particular execution paths affects feasibility, i.e., the probability of successful completion, and the expected number of superfluous activities that are planned but never executed. We frame the problem as a chance-constrained optimization problem and present two formulations: A decomposed approach with two stages, a planning stage that minimizes the expected number of superfluous activities subject to a feasibility constraint, and a scheduling stage that minimizes the makespan over the planned activities; and an integrated approach that combines planning and scheduling into a single formulation. Evaluation on two real-world and one synthetic dataset shows that the integrated approach yields superior makespans but is intractable at scale, while the decomposed approach scales to large settings.

Abstract

Decision-Making under Uncertainty

Explore similar work

Planning and Scheduling Business Processes under Control-Flow Uncertainty: Extended Version

DSevolve: Enabling Real-Time Adaptive Scheduling on Dynamic Flexible Job Shop with LLM-Evolved Heuristic Portfolios

DynaSchedBench: Calibrated Dynamic Scheduling Benchmarks and Observability Paradox in LLM-based Scheduling Agents