MISTA 2003 : Conference Programme
The plenary speakers will be
Order scheduling models can be described as follows. A machine environment (e.g., a number of non-identical machines in parallel) can produce a fixed variety of different products. Any one machine can process a given set of different product types. If it can process only one type of product it is referred to as a dedicated machine, otherwise it is referred to as a flexible machine. A flexible machine may be subject to a setup when it switches from one product type to another product type. Each product type has certain specific processing requirements on the various machines.
There are n customers, each one sending in one order. An order requests specific quantities of the various different products; it has a release date as well as a due date (committed shipping date). When the processing of all the different products. for an order have been completed, the order can be shipped.
We first introduce a notation for this class of models. We then focus on various different machine environments and several objective functions, including the total weighted completion time, the maximum lateness, the number of orders shipped late, and so on. We present polynomial time algorithms for some models, complexity proofs for problems that are NP-Hard, as well as heuristics with their worst case performance and empirical analyses.
We conclude with a number of practical applications of these models.
(This work is based on research done jointly with Joseph Leung and Haibing Li)
In recent years, scheduling research has had an increasing impact on practical problems, and a range of scheduling techniques have made their way into real-world application development. Constraint-based models now couple rich representational flexibility with highly scalable constraint management and search procedures. Similarly, mathematical programming tools are now capable of addressing problems of unprecedented scale, and meta-heuristics provide robust capabilities for schedule optimization. With these mounting successes and advances, it might be tempting to conclude that the chief technical hurdles underlying the scheduling problem have been overcome. However, such a conclusion (at best) presumes a rather narrow and specialized interpretation of scheduling, and (at worst) ignores much of the process and broader context of scheduling in most practical environments. In this note, I argue against this conclusion and outline several outstanding challenges for scheduling research.
We dicuss a number of polynomial time approximation results for scheduling problems. All presented results are based on the technique of rounding the optimal solution of an underlying linear programming relaxation. We analyze these relaxations, their intergrality gaps, and the resulting approximation algorithms, and we derive matching worst case instances.
Each presentation will be allocated a 30 minute slot (20 to 25 minutes presentation with 5 to 10 minutes for questions). Each conference room will have an OHP and a projector available (but not a laptop). If you are planning to present using an electronic format (e.g. powerpoint), you are advised to also bring acetates (for PHP presentation) in order to allow for unforeseen circumstances.The session chairs will be advised to strictly observe the time allocated to each presentation in order to allow for people to move between different streams. As presenters, you assistance in helping the session chairs would be appreciated.