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.
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
Brucker P
(2016)
Necessary and sufficient optimality conditions for scheduling unit time jobs on identical parallel machines
in Journal of Scheduling
Bruns F
(2016)
Complexity results for storage loading problems with stacking constraints
in European Journal of Operational Research
Condotta A
(2013)
Tabu search and lower bounds for a combined production-transportation problem
in Computers & Operations Research
Condotta A
(2014)
Scheduling patient appointments via multilevel template: A case study in chemotherapy
in Operations Research for Health Care
Knust S
(2019)
Shop scheduling problems with pliable jobs
in Journal of Scheduling
Li S
(2013)
A note on reverse scheduling with maximum lateness objective
in Journal of Scheduling
Weiss C.
(2016)
Flow shop and open shop scheduling with job splitting
Weiß C
(2017)
Open Shop Scheduling with Synchronization
in Journal of Scheduling
Weiß C
(2016)
Open Shop Scheduling with Synchronization
in Journal of Scheduling
Weiß C
(2016)
The assignment problem with nearly Monge arrays and incompatible partner indices
in Discrete Applied Mathematics
| 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 collaboration with Prof. Sigrid Knust continues earlier work 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. |
| 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. (2017) Journal of Scheduling 20, 557-581, 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" (2019) S. Knust, N.V. Shakhlevich, S. Waldherr, C. Weiß, Journal of Scheduling 22, 635-661. |
| Description | Collaborative Research with Prof. Peter Brucker |
| Organisation | University of Osnabrück |
| Country | Germany |
| Sector | Academic/University |
| PI Contribution | It was the joint research efforts of research collaborators, with the focus on underlying properties of the inverse scheduling models and on developing the methodology for solving them. The research took advantage of the discoveries and knowledge of Dr. Shakhlevich in the area of scheduling with variable parameters and the vast expertise of Prof. Brucker across a range of research topics in the area of scheduling and general combinatorial optimisation. |
| Collaborator Contribution | Prof. Brucker is the internationally leading researcher in the area of Scheduling. Apart from scheduling, his research interests cover other areas of combinatorial optimisation including linear programming, network flows, assignment, knapsack and clustering problems. The vast expertise of Prof. Brucker had led to the development of a new methodology for solving inverse problems. |
| Impact | Upon completion of the Inverse Scheduling project, the collaborators had successfully secured funding for a follow-up research within a new EPSRC project on Scheduling with Resource and Job Patterns. Unfortunately Prof. Brucker had sadly passed away in 2013, just a few a weeks before our first planned meeting within the new project. Joint work with Prof. Brucker had helped Dr. Shakhlevich in establishing strong collaborative links with the University of Osnabrueck, in particular with Prof. Sigrid Knust (a former PhD student of Prof. Peter Brucker). We consider our current work with Prof. Knust as a continuation of the research started with Prof. Brucker. One paper based on our joint research with Prof. Brucker was published after his death: Brucker, P., Shakhlevich, N.V. (2016) Necessary and sufficient optimality conditions for scheduling unit time jobs on identical parallel machines, Journal of Scheduling 19, 659-685. |
| Start Year | 2006 |
| 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). Prof. Gurevsky had made arrangements for my first visit to Nantes in 2018 which resulted in substantial further development of our study (optimisation under uncertainty) The second visit to Nantes was planned and arranged in 2020. Unfortunately that visit is placed on hold due to the travel restrictions in 2020-21. We continue collaboration online and are working now towards our first joint paper submission. |
| Collaborator Contribution | Formulating the concept of solution resiliency as a new stability measure. Resiliency analysis of general 0-1 combinatorial optimsation problems. First steps toward analysing scheduling problems. Further development of the general methodology for dealing with uncertainty. |
| 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/ |