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

Sep 4, 2026

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

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.

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

Ask PDF

Mar 29, 2026

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

In dynamic flexible job shops, order arrivals, machine breakdowns, and processing-time deviations continually reshape the scheduling state and the priority trade-offs behind dispatching decisions. Dispatching rules are well suited to this setting because they are fast, interpretable, and easy to deploy, and recent LLM-assisted automatic heuristic design further expands their expressiveness by evolving composite priority functions. The key challenge is to make these evolved rule behaviors state-adaptive without losing the rapid response needed for online rescheduling. This paper proposes a dynamic self-evolutionary framework DSevolve, which separates offline rule-library construction from online state-conditioned rule selection. Offline, an LLM-guided quality-diversity search combines multi-persona seeding, a MAP-Elites behavioral archive, and behavior-guided variation to evolve a library of complementary rules rather than a single elite, and event-level simulation then trains a neural selector to rank the rules by state. Online, after each rescheduling event, a neural selector maps a 22-dimensional state fingerprint to rule scores and dispatches the top-ranked rule within about a second, meeting the response-time requirement after each disruption. Experiments on dynamic instances derived from standard flexible job shop benchmarks show that DSevolve achieves lower mean makespan than individual LLM-evolved rules, classical dispatching rules, and learning-based baselines under a one-active-rule deployment protocol. Trained only on small instances, the selector transfers zero-shot to substantially larger dynamic shops. These results show that state-conditioned selection preserves the speed and interpretability of dispatching rules while improving adaptability.

XinLei Zhou, Jin Huang, Jie Yang +2

School of Mechanical Science and Engineering, Huazhong University of Science and Technology, Wuhan, 430074, PR China

Flexible Job Shop Scheduling Real-Time Scheduling Combinatorial Optimization Automated Heuristic Design Metaheuristic Optimization

Ask PDF

May 26, 2026

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

Progress in neural combinatorial optimization for Dynamic Flexible Job Shop Scheduling Problem (DFJSP) is currently hindered by a methodological tension: static benchmarks encourage benchmark overfitting, while uncalibrated generators obscure algorithmic capability with stochastic noise. To resolve this, we introduce DynaSchedBench, a diagnostic framework for DFJSP that rigorously controls the instance-generation process. Instead of relying on parameter sampling, our approach utilizes Sequential Event-Space Calibrator (SESC) that computes a novel Schedule Stress Index (SSI) to stratify instances by difficulty. We demonstrate that SESC is substantially more computationally efficient than evolutionary baselines while converging reliably to the target metrics. The framework integrates modular components for instance generation, snapshot-based simulation, agents, evaluation, and visualization, thereby enabling rigorous testing of reactive and lookahead-based policies. Leveraging this calibrated environment, we identify key limitations of LLM-based scheduling agents. Specifically, in step-wise online decision-making for dynamic scheduling, we identify an ``Observability Paradox'': providing agents with oracle access to full structural information can degrade policy performance, underperforming concise information. Furthermore, despite substantial token overhead, tool-augmented and refinement strategies fail to reliably improve performance, and most LLM agents fail to consistently surpass strong dispatching baselines-behaving more like robust heuristic approximators than superior optimizers.

Shijie Cao, Yuan Yuan, Jing Liu

School of Computer Science and Engineering, Beihang University, Beijing 100191, China · Shenzhen Loop Area Institute, Shenzhen, China · Qingdao Research Institute, Beihang University +3

LLM Agent Evaluation Combinatorial Optimization AI Agent Benchmarks Job Shop Scheduling Flexible Job Shop Scheduling

Ask PDF

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