Simulation / Learning Tool for Process Scheduling

Supervisor

Suitable for

Abstract

"In domains such as manufacturing there may be a large number of individual steps required to complete an overall task, with various constraints between the steps and finite availability of resources. For example, an aircraft may require hundreds of thousands of steps to build, with constraints like ""we cannot mount the engines before the wings"", and resources like the number of workers and pieces of key machinery. Scheduling software exists that takes the lists of steps, constraints, and resources and generates feasible schedules; that is, produces lists of which steps should be performed at what times. Given the complexity of the problem it is impractical to generate optimal schedules, but in general close to optimal schedules ('good schedules') can be generated in a reasonable time. However the choice of which good schedule to use is often determined by factors that are not known early in the process or are difficult to quantify, such as the layout of a factory or the temporary loss of a worker due to illness. The goal of this project is to take an existing scheduling program and a class of real-life industrial problems and to develop a simulation program that could assist a process engineer to visualise the similarities and differences between a small number of good schedules, and hence to interactively adjust the scheduling parameters in order to improve the schedule. For example the set of feasible schedules can be displayed as a graph with the steps as graph nodes, and a visualisation might show the progress of the schedule as annotations on the graph nodes, whilst providing a set of on-screen controls to adjust the scheduling parameters. The scheduling program itself is written in C++, but this does not constrain the simulation program to be written in a particular language. The skill-set required of a student taking this project would then be a mixture of two-dimensional graphics, plus a desire to find out more about two-dimensional animation and graphical user interface design. There is also the option of applying techniques from machine learning in order to automatically improve the schedule quality. The scheduling scenario to be used as an example in this project will be provided by an Oxford-based company who are interested in potentially applying these techniques in the future. On-line videos: https://www.promodel.com/solutionscafe/webinars/PCS_Quickstart/PCS_Quickstart.html gives a very simple example of the style of animation envisioned for this project, although we would expect the scheduling graph to be produced by the scheduling system rather than by hand as in this video. https://uk.mathworks.com/videos/simevents-for-operations-research-118566.html shows a Matlab extension (Simulink) on a more realistic example; this is without any animation but includes the use of machine learning in the form of a genetic algorithm."