Scheduling with Resource and Job Patterns

Lead Research Organisation: University of Leeds
Department Name: Sch of Computing

Abstract

The project will bring together two streams of scheduling research which involve patterns of different types: resource patterns and job patterns. Resource patterns are typical for personnel scheduling problems and for project management; job patterns are usually studied within machine scheduling. In spite of the differences in the nature of two types of patterns and the differences in application areas for two types of problems, there are a number of complementary features in the underlying models which have not been explored in the past. Within this project, we intend to complete the in-depth analysis of the two models, perform the knowledge exchange between the two areas and develop a new methodological framework for solving problems with patterns. The study of the separate problems with resource patterns and those with job patterns will be concluded with the study of the combined problem with both types of patterns, which models new features of real-world applications not studied before.

Planned Impact

The SRP and SJP models which we plan to study share important common features, but arise from different application areas. Historically, they were studied by two different research communities. If successful, our project will bring together the two research areas and address them in a systematic manner. Translating the results from one research area and making them applicable for the other area will enhance the solution toolkits for both problems and will stimulate the development of new methods for them. Furthermore, the project will make the first attempt to study the combined problem with resource patterns and job patterns which models new features of real-world problems not explored before.

Our research will lead to several research papers and one major review paper on the methodology of scheduling with patterns. Contrary to the existing survey papers on personnel scheduling in which problems are classified according to application areas (like hospitals, supermarkets, call centres, airports, police stations, etc.) we will classify problems with respect to the underlying patterns. Furthermore, our work on pathway scheduling and assembly job scheduling will cover application areas for which a theoretical background is still missing.

Publications

10 25 50
 
Description The following scheduling models were studied:
(A) optimisation aspects of the storage loading problem,
(B) open shop problem with synchronised job patterns,
(C) flow shop problem with flexible job patterns,
(D) optimisation problems with uncertain data.

Model (A) arises in several practical applications related to loading container terminals, container ships, warehouses or steel yards. In such problems incoming items arrive at a storage area by trains, vessels or trucks and have to be assigned to stacks. The typical constraints are
- only the topmost item of each stack can be directly retrieved,
- stacks should be build avoiding future reshuffling of containers,
- stack height is limited,
- items allocated to one stack should be compatible (not every item may be stacked on top of every other item).
We studied structural properties of the general model and its special cases. Besides providing polynomial time algorithms for some of these problems, we established the boundary to NP-hardness. Although the algorithms we proposed are designed for rather special situations, they can be used as building blocks for more general problems with additional features and constraints typical for real-world applications.

Model (B) arises in manufacturing with synchronised job patterns. An example of such a system, presented in the literature, is related to assembling shelf boards for kitchen elements. Another example arises in scheduling satellite communication. For the scheduling problem under study, we formulated the underlying model as a special multi-dimensional assignment problem, related to an important research area of optimisation problems with Monge-like arrays. We advanced the theoretical study of the assignment problem with nearly Monge arrays and demonstrated how our findings can be applied to the subject of our study, namely the open shop problem with synchronised job patterns.

The problems of type (C) arise in applications which admit some degree of flexibility in relocating parts of processing from one machine to another. The jobs are given by their processing times and processing patterns (open shop or to flow shop). The task is to split every job into operations and to sequence operations on processing machines in order to minimize a given objective function. In a fully flexible model, it is allowed to perform job splitting at any point; in a restricted model there are given lower and upper bounds on the lengths of operations. The main outcomes of our study are properties, reductions, complexity results and algorithms for various versions of the problem.

The problems of type (D) arise in the context of imprecise input information, when the key attributed of job patterns are known with some degree of uncertainty. The models we started to explore in 2016 jointly with Prof. Gurevsky and the Leeds team member Christian Weiss (PhD student at that time) differ substantially from traditional models of stochastic operational research, robust optimisation and stability analysis. Preserving some beneficial features of Stability Analysis, but relaxing strict optimality requirements of stability research, we proposed a new methodology capable of addressing problems with uncertain data that cannot be handled by existing methods. Our preliminary study has demonstrated the power of the proposed approach by considering several key combinatorial optimisation problems. We expect further research in this direction, formalising the proposed concepts and extending the range of problems it can address.

The outcomes of our research in areas (A) and (B) are published in Discrete Applied Mathematics, European Journal of Operational Research and Journal of Scheduling. The results for area (C) are presented at the 15th International Conference on Project Management and Scheduling (Valencia, Spain) and published in Journal of Scheduling.

To present the outcomes of our research in area (D) I was invited as plenary speaker to attend the International Conference "Mathematical Optimization Theory and Operations Research (MOTOR 2019, Ekaterinburg). The presentation was met with substantial interest and initiated new collaborations for future research.

Research in areas (B), (C) and (D) had led to a successful PhD thesis by Christian Weiss. He had his viva on 17 February 2017 and was recommended the award of PhD (subject to editorial and presentational corrections).
Exploitation Route The models we have studied are inspired by applications. The proposes algorithms can serve as the basis for the development of heuristics or as subroutines in more complex algorithms.
The most recent study of type (D) is particularly important as it helps handle problems with uncertain data.
Sectors Digital/Communication/Information Technologies (including Software),Manufacturing, including Industrial Biotechology,Transport

 
Description The outcomes in area (A) have influenced the study of the combined problems of manufacturing and air/surface transportation, rail transportation, maritime transportation limits, production and supply chain management. Another research area where our results are being used is related to container loading in sea terminals, warehouse environments and railroad terminals The project outcomes related to area (B) were presented at the main scheduling forum MAPSP'2015 (Methods and Algorithms for Planning and Scheduling Problems). It was discussed that our results are of potential impact in the area of fixed-parameter tractable (FPT) algorithms. We also expect that our research will have theoretical impact in the area of optimisation with Monge arrays. They are applicable to synchronisation of transmissions in satellite communication and in other areas with underlying models related to assignment problems. Results in area (C) can be used in making scheduling decisions in the presence of flexible machines, capable of performing operations of different types; the corresponding systems can be considered as generalisations of classical flow shops and open shops. Research in area (D) is particularly important for applications as it provides a powerful methodology for handling optimisation problems with uncertain parameters. We expect its impact will become visible in few years.
First Year Of Impact 2016
Sector Digital/Communication/Information Technologies (including Software),Manufacturing, including Industrial Biotechology,Transport
Impact Types Economic

 
Description Collaboration with Prof. Sigrid Knust and her research group 
Organisation University of Osnabrück
Country Germany 
Sector Academic/University 
PI Contribution Our current work with Prof. Sigrid Knust can be considered as a continuation of the research started with Prof. Peter Brucker, who tragically passed away in 2013. Our joint work includes theoretical study of scheduling models with such special features and (a) synchronisation, (b) job splitting, and the underlying combinatorial optimisation problems, as well as applied models, e.g., (c) loading problems at containers terminals. Several papers are already published; the most recent one was accepted for publication in March 2019.
Collaborator Contribution Prof. Sigrid Knust had made steps to extend our collaborative research, organising seminars in Osnabrueck with several members of her team. Eventually two members of the Osnabrueck team have become actively involved into our joint research: - Dr. Florian Bruns contributing to (c) - Dr. Stefan Waldherr contributing to (a) and (b). In addition to several meetings in Osnabrueck, Prof. Sigrid Knust visited Leeds in May 2015. Dr. Stefan Waldherr visited our group in November 2013 and November 2015.
Impact 1) "Complexity results for storage loading problems with stacking constraints" Bruns, F., Knust, S., and Shakhlevich, N.V. , European Journal of Operational Research 249, 1074-1081, 2016, doi.org/10.1016/j.orhc.2014.02.002. 2) "The assignment problem with nearly Monge arrays and incompatible partner indices" Weiss, C., Knust, S., Shakhlevich, N.V., Waldherr, S., Discrete Applied Mathematics, 211, 183-203, 2016, http://dx.doi.org/10.1016/j.dam.2016.04.019 3) "Open shop scheduling with synchronization" by Weiß, C., Waldherr, S., Knust, S., Shakhlevich, N.V. (Journal of Scheduling, accepted, doi.org/110.1007/s10951-016-0490-0) 4) "On the assignment problem with a nearly Monge matrix and its applications in scheduling" by Weiß, C., Knust, S., Shakhlevich, N., Waldherr, S. (presentation, 12th Workshop on Models and Algorithms for Planning and Scheduling Problems, 2015, La Roche-en-Ardenne, Belgium) 5) "Flow shop and open shop scheduling with job splitting" by Weiß, C., Knust, S., Shakhlevich, N.V., Waldherr, S. (presentation, 15th International Conference on Project Management and Scheduling, 2016, Valencia, Spain) 6) "Flow shop and open shop scheduling with pliable jobs", S. Knust, N.V. Shakhlevich, S. Waldherr, C. Weiß (accepted by Journal of Scheduling).
 
Description Collaborative research with Dr. Evgeny Gurevsky 
Organisation University of Nantes
Country France 
Sector Academic/University 
PI Contribution We started collaborative research with Dr. Evgeny Gurevsky from the University of Nantes in 2016, when Dr. Gurevsky visited our group in Leeds for one week. A new research direction that had emerged as a result of that visit is a study of new stability measures in combinatorial optimisation. The first paper is under preparation. As invited speaker, I presented the main outcomes of our study at the International Conference "Mathematical Optimization Theory and Operations Research (MOTOR 2019, Ekaterinburg).
Collaborator Contribution Formulating the concept of solution resiliency as a new stability measure and its preliminary study in the context of assembly line scheduling.
Impact The main output are the two research papers which are under preparation.
Start Year 2016
 
Description A number of conference presentations 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Other audiences
Results and Impact The outcomes were presented at the main international scheduling forums:

Weiss, C., Knust, S., Shakhlevich, N.V., and Waldherr, S. On the assignment problem with a nearly Monge matrix and its applications in scheduling, 12th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP'2015), La Roche-en-Ardenne, Belgium, 2015, pp. 143-145.

Weiss, C., Knust, S., Shakhlevich, N.V., and Waldherr, S. Flow shop and open shop scheduling with job splitting (PMS'2016) 12th Workshop on Models and Algorithms for Planning and Scheduling Problems, Valencia, Spain, 2016, pp. 26-29.
Year(s) Of Engagement Activity 2014,2015,2016
 
Description Invited talk at the International Conference "Mathematical Optimization Theory and Operations Research (MOTOR 2019, Ekaterinburg) 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Other audiences
Results and Impact I presented my new research direction, joint with Dr. Christian Weiss and Dr. Evgeny Gurevsky, which stems from the EPSRC funded project "Scheduling with Resource and Job Patterns".
The talk was entitled "On a New Approach for Optimization under Uncertainty", and it raised substantial interest from the research community.
As the outcome of the talk, I expect new international collaborations with Prof. Alexander Kononov (Novosibirsk, Russia) and Prof. Bertrand Lin (Taiwan).
Prof. Kononov intends to visit me in August 2020 to start new research on the subject I presented at MOTOR'2019.
We have started collaboration with Prof. Bertrand Lin on the subject he presented at MOTOR'2019, also as invited speaker.
Year(s) Of Engagement Activity 2019
URL http://motor2019.uran.ru/
 
Description On General Methodology for Solving Inverse Scheduling Problems 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Other academic audiences (collaborators, peers etc.)
Results and Impact Dr. Shakhlevich made a presentation at the workshop New Challenges in Scheduling Theory (March 31 - April 4, 2014, Aussois, France).
Presenting the key findings of the research project at the event which is of the type "by invitation only" was highly important in disseminating the results.

The talk had raised the awareness of the scheduling community on Inverse Optimisation research and helped in identifying the directions on how the work can be developed further.
Year(s) Of Engagement Activity 2014
URL http://aussois2014.imag.fr/