Prediction-based Resource Allocation using LSTM and Minimum Cost and Maximum Flow Algorithm

Gyunam Park; Minseok Song

doi:10.1109/ICPM.2019.00027

Prediction-based Resource Allocation using LSTM and Minimum Cost and Maximum Flow Algorithm

Gyunam Park, Minseok Song

June, 2019

Abstract

Predictive business process monitoring aims at providing the predictions about running instances by analyzing logs of completed cases of a business process. Recently, a lot of research focuses on increasing productivity and efficiency in a business process by forecasting potential problems during its executions. However, most of the studies lack suggesting concrete actions to improve the process. They leave it up to the subjective judgment of a user. In this paper, we propose a novel method to connect the results from predictive business process monitoring to actual business process improvements. More in detail, we optimize the resource allocation in a non-clairvoyant online environment, where we have limited information required for scheduling, by exploiting the predictions. The proposed method integrates offline prediction model construction that predicts the processing time and the next activity of an ongoing instance using LSTM with online resource allocation that is extended from the minimum cost and maximum flow algorithm. To validate the proposed method, we performed experiments using an artificial event log and a real-life event log from a global financial organization.

Type

Conference paper

Publication

2019 International Conference on Process Mining

Practical problem

Hospitals, banks and other service organizations must decide many times a day which staff member takes which pending task, and a poor choice lengthens waiting for everyone, especially urgent cases. Scheduling heuristics from manufacturing assume the processing time and the next step of every job are known in advance, but in an emergency department or a loan desk nobody knows how long the current step will take or what the next one will be until it happens. Predictive monitoring tools can forecast such quantities, yet they stop at the forecast and leave the decision to the manager’s judgment. The gap between a prediction and a concrete allocation decision therefore remains open in practice.

Research questions

How can prediction models supply the scheduling parameters, namely processing time and next activity, that are unknown in a non-clairvoyant online environment?
How can resources be dispatched efficiently on the basis of these predictions so that total weighted completion time is minimized?

Contributions

Formulates resource allocation in business processes as a non-clairvoyant online job shop scheduling problem that minimizes total weighted completion time under limited information.
A two-phase method: offline training of a multi-task Long Short-Term Memory (LSTM) network that predicts processing time and next activity from one-hot encoded prefixes, and online scheduling driven by an event stream.
A scheduling algorithm that builds a bipartite graph of ready and predicted work items versus resources, with edge cost (processing time plus readiness penalty) divided by instance weight, and solves minimum cost maximum flow with the network simplex method.
Pseudo-assignments that reserve resources for predicted high-weight work items before they are released, followed by execution of the matches whose instance and resource are both available.
An evaluation against a WeightGreedy first-come-first-served baseline on a simulated emergency department log and the BPI Challenge 2012 loan application log.

Key findings

On the simulated emergency department (11 activities, 25 resources, 1,000 training patients, stream of 100 patients) the method beats WeightGreedy for every number of instances; at 80 instances the baseline total weighted completion time of 28,393 is 14 percent above the method’s 24,804.
On one day of manual work items from BPI Challenge 2012 (110 instances, about 3 activities each, weights from 10 requested-amount buckets) total weighted completion time falls from 1,479 for the baseline to 1,038, i.e. the baseline is 42 percent higher.
The gain costs computation: 115.6 seconds versus 7.6 for the baseline on the real log, with 110.1 seconds spent on predictions because every work item has many candidate resources.
Limitation: the method depends on prediction quality; a wrong processing-time prediction assigns the work item to a suboptimal resource, and repeated prediction for every newly released instance dominates runtime.