MISTA 2009 Programme

The draft program is now available from here.

Plenary Speakers


Edmund Burke
Edmund Burke, University of Nottingham, UK
A comparison of two methods for reducing take-off delay at London Heathrow airport
Abstract: This paper describes recent research into the departure process at London Heathrow, with the primary motivation of reducing the amount of fuel used, improving both the economic and environmental cost. Two proposals are considered here. The first proposal considers the practicality and potential benefits of aiding the controller to improve the take-off sequencing. The second proposal aims to absorb some of the inevitable delay for aircraft at the stands, before the engines are started, but also involves a take-off sequencing aspect. Models for the two take-off sequencing problems are presented in this paper, the second of which includes an additional pushback time (or TSAT) allocation sub-problem which has to be solved subsequently. These models have distinctive differences from the models for the takeoff and arrival sequencing problems which are usually considered in the literature, since they take into account necessary constraints imposed due to the control problem (whether a sequence can actually be achieved, and how) in each case. As discussed in this paper, the control problem cannot be ignored by the controllers at Heathrow, so cannot be ignored by any realistic system to aid them in their tasks. Comparative take-off sequencing results are presented for the two systems and the potential benefits from providing decision support to the runway controllers or improved TSAT allocation at the stands are considered. The paper ends with some overall conclusions from the research, showing the large potential benefits of these systems. The TSAT allocation system which is discussed in this paper has been developed for implementation at London Heathrow as one element of the Collaborative Decision Making project.


Anonymous
David Hine, Metropolitan Police, UK
Title: Football Sports Scheduling in the Real World (provisional title)
Abstract: A full abstract will be posted shortly but David will talk about his role in the Metropolitan in scheduling football fixtures (and other resources) in order to minimise costs as well as public disorder.


Moshe Dror
Moshe Dror, University of Arizona, USA
Title: ‘Strong’ - ‘Weak’ Precedence in Job Scheduling
Abstract: It is common knowledge that most applied combinatorial optimization problems with partial orders are NP-hard. Special cases of partial orders have been considered in great detail, permitting us to focus on an interesting precedence order distinction in scheduling. In this talk we will examine a partial order delineation of ‘strong’ and ‘weak’ precedence in chain and tree precedence structures.
We will present a summary of results regarding NP-hardness and polynomial time solvability for the distinction between ‘strong’ and ‘weak’ precedence in scheduling. In many cases, NP-hardness for weak precedence implies NP-hardness for the strong precedence. However, this is not universally true, and the ‘strong’ - ‘weak’ distinction is proper - at least for the case of chains. We primarily focus on the results for chains and trees but extend the 'strong’ - ‘weak’ precedence distinction to more general digraphs grounded in and motivated by actual real-life dispatching in multiprocessing systems that require stable schedules.


Raymond Kwan
Raymond Kwan, University of Leeds, UK
Title: Case studies of successful train crew scheduling optimization
Abstract: The UK has a very large and complex passenger rail network divided into a number of franchises. Train crew scheduling is mission critical to the train operating companies, which would feel the pain if they have to schedule manually. Until recent years, none of the few attempts by these companies to adopt an automatic optimizing train crew scheduling system was successful. Typically, systems were commissioned based on their potentials but then they were unable to deliver schedules of acceptable quality, and they were eventually abandoned by the train companies. The TrainTRACS system has changed the scenario. ScotRail adopted TrainTRACS in 2003 and has remained an active user to date. This success has spread rapidly by the University of Leeds spin-out company Tracsis Plc, and now most of the major UK train operating companies are using TrainTRACS. This paper presents case studies of recent pilot trials for new Tracsis clients to adopt TrainTRACS, highlighting some special scheduling situations encountered.

Regular Talks

This is the list of all the presentations that will take place at the conference

  • (121) Abd-Aziz Z. and Kendall G. An Investigation of an Ant-based Hyperheuristic for the Capacitated Vehicle Routing Problem
  • (120) Abdul-Hamid N.H., Kendall G. and Sagir M. Mathematical Modeling for Maximising Gate Receipt Problem
  • (079) Abdullah S., Turabieh H., McCollum B. and Burke E.K. An investigation of a Genetic Algorithm and Sequential Local Search Approach for the Curriculum-Based Course Timetabling Problem
  • (119) Aggoune R. and Mati Y. Recent Advances in Solving Two-Job Shop Scheduling Problems: Extensions and Improvements of the Geometric Approach
  • (113) Al-Betar M.A. and Khader A.T. A hybrid harmony search for university course timetabling
  • (034) Almeder C., Katzensteiner S. and Hartl R.F. A VNS-Based Solution Approach for a Flexible Flow Shop Problem with Limited Buffer
  • (068) Alsheddy A. and Tsang E. Empowerment-based Workforce Scheduling Problem
  • (901) Atkin J.A.D., Burke E.K. and Greenwood J.S. A Comparison of Two Methods for Reducing Take-Off Delay at London Heathrow Airport
  • (004) Baker K.R. and Trietsch D. Three Heuristic Procedures for the Stochastic Flow Shop Problem
  • (041) Barták R. and Skalický T. A local Approach to Automated Correction of Violated Precedence and Resource Constraints in Manually Altered Schedules
  • (097) Beliën J. and Demeulemeester E. Integrated Workforce Staffing and Scheduling: A Case Study at a Major Aircraft Maintenance Company
  • (049) Benabid A. and Hanen C. Decomposed Software Pipelining for Cyclic Unitary RCPSP with Precedence Delays.
  • (088) Berghman L. and Leus R. Solving a Dock Assignment Problem as a Three-Stage Flexible Flow-Shop Problem
  • (020) Berlinska J. and Drozdowski M. Heuristics for Divisible Loads Scheduling in Systems with Limited Memory
  • (028) Bilgin B., De Causmaecker P. and Vanden Berghe G. A Hyperheuristic Approach to Belgian Nurse Rostering Problems
  • (051) Bini E. Modeling Preemptive EDF and FP by Integer Variables
  • (047) Blazewicz J., Machowiak M. and Oguz C. Approximation Algorithm for Berth and Quay Crane Allocation Problem with Bounds
  • (007) Borgulya I. Solving the Undirected Capacitated Arc Routing Problem with a Memory Based Method
  • (063) Bozejko W., Uchronski M. and Wodecki M. Scatter Search for a Weighted Tardiness Flow Shop Problem
  • (062) Bril R.J., Cucu-Grosjean L. and Goossens J. Response Time Analysis in Distributed Real-Time Systems: An Improvement Based on Best-Case Finalization Time Analysis
  • (112) Burke E.K., Curtois T., Hyde M., Kendall G., Ochoa G., Petrovic S. and Vázquez-Rodriguez J.A. HyFlex: A Flexible Framework for the Design and Analysis of Hyper-Heuristics
  • (099) Burke E.K., Qu R. and Soghier A. Adaptive Selection of Heuristics within a GRASP for Exam Timetabling Problems
  • (016) Ceschia S. and Schaerf A. Tabu Search Techniques for the Heterogeneous Vehicle Routing Problem with Time Windows and Carrier-Dependent Costs
  • (027) Chen S-H., Chen M-C., Chang P-C., Zhang Q. and Chen Y-M. Development of Effective Estimation of Distribution Algorithms for Scheduling Problems
  • (019) Ciavotta M., Ruiz R. and Minella G. New Results for the Multi-Objective Sequence Dependent Setup Times Flowshop Problem
  • (074) Creemers S., De Reyck B., Lambrecht M. and Leus R. Project Scheduling with Alternative Technologies and Stochastic Activity Durations
  • (048) Detienne B., Dauzčre-Pérčs S. and Yugma C. Scheduling Inspection Operations Subject to a Fixed Production Schedule
  • (026) Dožic S., Kalic M., Babic O. and Cangalovic M. Heuristic Approach to the Airline Schedule Disturbances Problem: Multi-Fleet Case
  • (902) Dror M. and Steiner G. ‘Strong’-‘Weak’ Precedence in Scheduling: Extended Order Implications
  • (064) Duša V. and Barták R. Preemptive Scheduling with Precedences and Alternative Resources
  • (043) Elvikis D., Hamacher H.W. and T’kindt V. Scheduling Two Interfering Job Sets on Uniform Parallel Machines with Makespan and Cost Functions
  • (107) Fowler J.W., Gul S., Denton B.T. and Huschka T.R. Bi-Criteria Scheduling of an Outpatient Procedure Center
  • (076) Gather T. and Zimmermann J. Exact Methods for the Resource Levelling Problem
  • (090) Gendreau M., Côté J-F. and Potvin J-Y. An Effective Heuristic for the Pickup and Delivery Traveling Salesman Problem with LIFO Loading and Multiple Stacks
  • (125) Glass C. and Chakhlevitch K. Scheduling in a Micro-Biological Laboratory: Heuristics for Sequencing Food Sample Tests, to Co-ordinate with Production of Perishable Media Materials
  • (066) Gomes M.C., Barbosa-Póvoa A. and Novais A.Q. Scheduling of Job Shop, Make-to-Order Industries with Recirculation and Assembly: Discrete Versus Continuous Time Models
  • (006) Goossens D.R. and Spieksma F.C.R. Soccer Schedules in Europe: An Overview
  • (100) Guedes A.C.B. and Ribeiro C.C. A Heuristic for Minimizing Weighted Carry-Over Effects in Round Robin Tournaments
  • (053) Guitouni A. and Masri H. A Nonlinear Mixed Integer Program for Search Path Planning Problem (SPPP)
  • (036) Gunawan A. and Lau H.C. Master Physician Scheduling Problem
  • (003) Günther H-O. An MILP-Based Approach to Short-Term Production Scheduling and Lot Sizing with Major and Minor Setups: A Case Study from the Beverage Industry
  • (101a) Hanzálek Z. and Šucha P. Time Symmetry of Project Scheduling with Time Windows and Take-Give Resources
  • (101b) Kutil M., Šucha P., Capek R. and Hanzálek Z. TORSCHE Scheduling Toolbox for Matlab
  • (109) Haspeslagh S., De Causmaecker P. and Vanden Berghe G. A Multi-Agent System Handling Personnel Shortages in Hospitals
  • (045) Hazir O., Kedad-Sidhoum S. and Chrétienne P. Batching and Scheduling with Tardiness Penalties
  • (029) Herrmann J.W. Generating Cyclic Fair Sequences for Multiple Servers
  • (039) Hieu T.T. and Ming N.K. A Water Flow Algorithm for Flexible Flow Shop Scheduling with Limited Intermediate Buffers
  • (904) Hine D. Resource Scheduling for Policing for Football Matches
  • (021) Hurink J.L., Kok A.L., Paulus J.J. and Schutten J.M.J. Time-Constrained Project Scheduling with Adjacent Resources
  • (096) Hyde M., Özcan E. and Burke E.K. Multilevel Search for Evolving the Acceptance Criteria of a Hyper-Heuristic
  • (044) Jat S.N. and Yang S. A Guided Search Genetic Algorithm for the University Course Timetabling Problem
  • (023) Juraszek J., Pesch E. and Sterna M. Simulated Annealing Method for Maximizing Revenue on Parallel Machines
  • (110) Kergosien Y., Lenté C. and Billaut J-C. Home Health Care Problem: An Extended Multiple Traveling Salesman Problem
  • (105) Khowala K., Fowler J., Keha A. and Balasubramanian H. Single Machine Scheduling with Interfering Job Sets
  • (012) Kravchenko S.A. and Werner F. Parallel Machine Problems with Equal Processing Times
  • (086) Kvaratskhelia A. and Lazarev A. Polynomial Algorithm for 1 | rj,pj = p, pmnt | S wicj Scheduling Problem
  • (903) Kwan R.S.K. Case Studies of Successful Train Crew Scheduling
  • (075) Lazarev A.A. and Gafarov E.R. Estimation of Absolute Error for the Resources-Constrained Project Scheduling Problem
  • (073) Lehoux-Lebacque V., Brauner N. and Finke G. Polynomial Complexity of the Cyclic Identical Coupled Task Problem
  • (131) Lewis R. and Thompson J. Round-Robin Sports Scheduling from a Graph Colouring Perspective: A Case Study in Rugby Union Scheduling
  • (117) Lin E.Y.H. On the Effective Approach of Teaching Activity Scheduling in Project Management
  • (093) Lřkketangen A., Haugen K., Lanquepin G. and Olstad A. Using a Set of Fixed Prices when Solving Profit Maximization Capacitated Lot-Size Problems (PCLSP)
  • (052) Maenhout B. and Vanhoucke M. Reactive Nurse Scheduling in Hospitals
  • (122) McCollum B., Kendall G., McMullan P. and McGoldrick J. Decision Support Systems for Tankering within the Airline Industry
  • (118) McCollum B., Kwan R.S.K. and McMullan P.J. Real World Optimisation through Spin Out Activity
  • (116) McCollum B., McMullan P.J., Parkes A.J., Burke E.K. and Abdullah S. An Extended Great Deluge Approach to the Examination Timetabling Problem
  • (069) Mokotoff E. Minimizing the Makespan and Total Flow Time on the Permutation Flow Shop Scheduling Problem
  • (070) Mönch L. and Almeder C. Ant Colony Optimization Approaches for Scheduling Jobs with Incompatible Families on Parallel Batch Machines
  • (104) Mönch L., Fowler J.W., Dauzčre-Pérčs S., Mason S.J. and Rose O. Scheduling Semiconductor Manufacturing Operations: Problems, Solution Techniques, and Future Challenges
  • (095) Müller T., Rudová H. and Murray K. Interactive Course Timetabling
  • (022) Nishi T. and Hiranaka Y. Lagrangian Relaxation and Cut Generation for Sequence Dependent Setup Time Flowshop Scheduling Problems
  • (015) Nobibon F.T., Herbots J. and Leus R. Order Acceptance and Scheduling in a Single-Machine Environment: Exact and Heuristic Algorithms
  • (030) Oguz C. and Narin Ö. Solving Berth Allocation Problem with Column Generation
  • (072) Ormsbee L., Lingireddy S. and Chase D. Optimal Pump Scheduling for Water Distribution Systems
  • (103) Osman I.H., Belouadah H., Fleszar K. and Saffar M. Hybrid of the Weighted Minimum Slack and Shortest Processing Time Dispatching Rules for the Total Weighted Tardiness Single Machine Scheduling Problem with Availability Constraints
  • (038) Ourari S., Briand C. and Bouzouia B. Minimizing the Number of Tardy Jobs in Single Machine Scheduling using MIP
  • (077) Özcan E. and Burke E.K. Multilevel Search for Choosing Hyper-Heuristics
  • (085) Özcan E., Misir M. and Burke E.K. A Self-Organising Hyper-heuristic Framework
  • (024) Papa G. and Korošec P. Metaheuristic Approach to Loading Schedule Problem
  • (017) Pappis C.P., Rachaniotis N.P. and Dasaklis T. A Deterministic Resource Scheduling Model in Epidemic Logistics
  • (114) Parkes A.J., McCollum B., McMullan P. and Burke E.K. Recent Work on Planning and Management of University Teaching Space
  • (094) Pawlak G. and Rucinski M. Single Machine Re-Entrant Jobs Scheduling in the Car Factory Paint Shop
  • (089) Pillay N. Evolving Hyper-Heuristics for the Uncapacitated Examination Timetabling Problem
  • (092) Qu R., He F. and Burke E.K. Hybridizing Integer Programming Models within an Adaptive Decomposition Approach for Exam Timetabling Problems
  • (014) Rudec T., Baumgartner A. and Manger R. Speeding up the Optimal Off-Line Algorithm for Solving the k-server Problem
  • (083) Ruiz R. and Naderi B. Variable Neighborhood Descent Methods for the Distributed Permutation Flowshop Problem
  • (123) Sabar N.R., Ayob M. and Kendall G. Solving Examination Timetabling Problems using Honey-Bee Mating Optimization (ETP-HBMO)
  • (127) Santos C.A., Zhang A., Gonzalez M.T., Jain S. and Byde A. Workforce Planning and Scheduling for the HP IT Services Business
  • (078) Schwiegelshohn U. An Owner-Centric Metric for the Evaluation of Online Job Schedules
  • (061) Serafini P. On some Combinatorial Properties of PESP
  • (001) Shabtay D. and Steiner G. Bicriteria Models to Minimize the Total Weighted Number of Tardy Jobs with Convex Controllable Processing Times and Common Due Date Assignment
  • (008) Simonin G., Darties B., Giroudeau R. and König J-C. Isomorphic Coupled-Task Scheduling Problem with Compatibility Constraints on a Single Processor
  • (018) Sterna M. and Juraszek J. Scheduling Policy for On-Line Translation Service
  • (040) Tanaka S. and Sato S. An Exact Algorithm for the Precedence-Constrained Single-Machine Scheduling Problem
  • (002) Vakhania N. Scheduling Jobs with Release Times Preemptively on a Single Machine to Minimize the Number of Late Jobs
  • (132) Vakhania N. An Efficient Implicit Enumeration for Scheduling Equal-Length Jobs with Release Times on a Single Processor to Maximize Throughput
  • (124) Weeks K.O., Gao H., Alidaee B. and Rana D. An Empirical Study of Impacts of Production Mix Efficiency, Product Route Efficiency on Operations Performance and Profitability: A Reverse Logistics Approach.
  • (032) Xu Y. and Qu R. A GRASP Approach for the Delay-Constrained Multicast Routing Problem
  • (033) Yomsi P.M. and Sorel Y. Schedulability Analysis for non Necessarily Harmonic Real-Time Systems with Precedence and Strict Periodicity Constraints using the Exact Number of Preemptions and no Idle Time
  • (057) Zerola M., Barták R., Lauret J. and Šumbera M. Planning Heuristics for Efficient Data Movement on the Grid