Inverse Optimisation in Application to Scheduling
Lead Research Organisation:
University of Leeds
Department Name: Sch of Computing
Abstract
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.
Publications
Brucker P
(2009)
A polynomial-time algorithm for a flow-shop batching problem with equal-length operations
in Journal of Scheduling
Brucker P
(2010)
Inverse scheduling: two-machine flow-shop problem
in Journal of Scheduling
Brucker P
(2009)
Inverse scheduling with maximum lateness objective
in Journal of Scheduling
Brucker P
(2016)
Necessary and sufficient optimality conditions for scheduling unit time jobs on identical parallel machines
in Journal of Scheduling
N.V. Shakhlevich (Author)
(2006)
Inverse Optimization in Scheduling
in Proceedings of the 21st European Conference on Operational Research (EURO XXI
P. Brucker
(2007)
Inverse scheduling with maximum lateness objective
in Proceedings of the XX European Chapter on Combinatorial Optimization (ECCO)
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)
P. Brucker (Co-Author)
(2008)
Inverse Model of the Flow Shop Scheduling Problem
in Proceedings of the XXI European Chapter on Combinatorial Optimization ECCO
Wen Z
(2022)
Orchestrating Networked Machine Learning Applications Using Autosteer
in IEEE Internet Computing
| 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 |
| URL | http://aussois2014.imag.fr/ |