Inverse Optimisation in Application to Scheduling

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


In recent years, the interest in inverse optimisation has increased dramatically. Unlike traditional optimisation models for which all parameters are given and the objective is to find the best solution subject to certain constraints, in inverse optimisation the exact values of some parameters are unknown and they should be determined so that a pre-specified solution becomes optimal. While inverse optimisation has attracted much attention of researchers in different areas of combinatorial optimisation, scheduling problems have not yet been studied in terms of inverse optimisation. The outcomes of this project will advance inverse optimisation research in the area of scheduling and will contribute to the UK's prominence in this newly emerging research direction.


10 25 50
publication icon
Brucker P (2009) Inverse scheduling with maximum lateness objective in Journal of Scheduling

publication icon
Brucker P (2010) Inverse scheduling: two-machine flow-shop problem in Journal of Scheduling

publication icon
N.V. Shakhlevich (Author) (2006) Inverse Optimization in Scheduling in Proceedings of the 21st European Conference on Operational Research (EURO XXI

publication icon
P. Brucker (2007) Inverse scheduling with maximum lateness objective in Proceedings of the 8th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP'2007)

publication icon
P. Brucker (2007) Inverse scheduling with maximum lateness objective in Proceedings of the XX European Chapter on Combinatorial Optimization (ECCO)

publication icon
P. Brucker (Co-Author) (2008) Inverse Model of the Flow Shop Scheduling Problem in Proceedings of the XXI European Chapter on Combinatorial Optimization ECCO

Description This project supported our collaborative research with Prof. Peter Brucker, one of the leading experts in scheduling and combinatorial optimisation. The project was aimed at extending a new direction of research - inverse optimisation - to the area of scheduling and it has successfully achieved its goal.

At the time of preparing the project proposal we were not aware of any inverse scheduling results. Throughout our work we have found only one paper by C. Koulamas (2005) on a very restrictive.
Exploitation Route The research conducted is mainly of theoretical nature. Potential applications are related to scheduling decisions in manufacturing and services. Due to the theoretical nature of our research, the main exploitation route for us is publishing project outcomes in high quality journals and presenting the results at the top international conferences. Our main results are published in the Journal of Scheduling, which is the leading journal in the area of Scheduling.
Sectors Digital/Communication/Information Technologies (including Software),Other

Description The project provided the first theoretical insight into the study of Inverse Optimisation problems in the area of Scheduling.
First Year Of Impact 2007
Sector Other
Description International Collaboration 
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.
Start Year 2006
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