Abstracts - Latest Developments in Scheduling Research and Practice

Ravindra K. Ahuja, President, Innovative Scheduling, Inc.

Recent Advances in Transportation Scheduling

Most of the complex real-world scheduling problems in transportation are still solved manually due to the unavailability of satisfactory algorithms to solve these problems. These problems are essentially very large-scale multi-commodity flow network design and routing problems. In this presentation, we will give an overview of some scheduling problems that we have studied and solved successfully in the past few years. We will outline our algorithmic approaches, present computational results, and share lessons learnt is putting the results of our algorithms into practice.  

Vahab Mirrokni, Google Research

Coordination Mechanisms for Selfish Scheduling Problems

We investigate the influence of different algorithmic choices on the approximation ratio in selfish scheduling, and survey the recently developed results about coordination mechanisms for machine scheduling. Our goal is to design local policies that minimize the inefficiency of resulting equilibria. For unrelated machine scheduling, we show that connection of results for shortest-first policy to an open question raised by Ibarra and Kim, and Davis and Jaffe. Finally, we present the first coordination mechanisms achieving a logarithmic bound for makespan over unrelated machines. Time-permitting, I will also describe recent results for sum-of-completion-times social function in this context.

Viswanath Nagarajan, IBM Research

Minimum Makespan Multi-vehicle Dial-a-Ride

Dial-a-Ride problems involve moving a set of objects from their sources to respective destinations. We study the multi-vehicle Dial-a-Ride problem with transshipments. There is a fleet of identical vehicles used to move objects, with each vehicle initially located at its own depot-vertex. Additionally, objects may be left at intermediate vertices and transported by multiple vehicles. The objective is to find a feasible schedule (i.e. a capacitated route for each vehicle, that together move all objects from their sources to destinations) of minimum makespan. We present an approximation algorithm for this problem achieving a poly-logarithmic performance guarantee.

This is joint work with Inge Li Goertz and R. Ravi.

Alkiviadis Vazacopoulos, FICO

Using Mixed Integer Programming to Solve Sequencing, Scheduling and Packing Problems

Recent advancements in Mixed Integer Programming solvers give us the ability to solve larger and more complex sequencing , scheduling and packing problems. We will demonstrate this fact by showing examples from tournament scheduling, space retail optimization, production scheduling and sequencing in energy applications.

J. Christopher Beck, University of Toronto

Combining Constraint Programming and Local Search for Job-Shop Scheduling

Sophisticated metaheuristics represent the state-of-the-art in job shop scheduling. Inspired by these algorithms, a solution-guided constructive search approach has been proposed in the constraint programming literature. When applied to job shop scheduling, the algorithm exhibits strong performance, but still lags the state-of-the-art. We examine a simple hybridization of solution-guided constructive search with an existing metaheuristic-based scheduler. Despite the simplicity of the hybridization, we observe very strong results, finding 10 new best solutions for a well-known benchmark set. Of particular note is the fact that the hybrid exhibits very low variance across multiple runs and, because it is complete, for the first time, we are able to prove optimality on a number of problem instances.

Joint work with T.K. Feng, University of Toronto & Jean-Paul Watson, Sandia National Laboratories

Zhi-Long Chen, Robert H. Smith School of Business, University of Maryland

Integrated Production and Distribution Scheduling with Fixed Delivery Departure Dates

We consider an integrated production-distribution scheduling model where delivery vehicles have fixed departure dates.  Applications include assembly and delivery of make-to-order consumer electronics products, and processing and delivery of mails. In such a problem, order processing and delivery operations need to be scheduled jointly in order to achieve a satisfactory delivery performance at minimum transportation cost. We consider several problems by investigating computational complexity and optimality properties. Some of the problems can be solved in polynomial time, whereas some other problems are NP-hard. We will also point out some directions for future research.

Sudipto Guha, University of Pennsylvania

Standard Stochastic Scheduling with Additional "Probing" Operations to Resolve Uncertainty

Standard stochastic scheduling is used in sensor network type applications. The stochastic component is reduced to some deterministic "effective" measure. This builds upon much of the research in online stochastic settings, however the probe aspect is new. Interestingly, some parts of this concept can be used in optimization problems in the ad-exchanges considered by Google, Yahoo, and other online search engines. There is a clear connection here with sensing/guessing bids.

Pascal van Hentenrijck, Brown University

Constraint-Based Scheduling: Recent Results

This talk reviews recent progress in constraint-based scheduling on a variety of scheduling problems. The applications considered include job shop and flexible shop problems, just-in-time scheduling, and scheduling problems in emergency response.

Andreas Schultz, MIT

Single-Machine Scheduling with Precedence Constraints: A Case Study in Combinatorial Optimization

The time has come to take stock of some 40 years of research on this classic sequencing problem. I will take us on a tour of some of the most relevant, beautiful and surprising results. Along the way, we will encounter min cuts, b-matchings, vertex covers, graph colorings, binary problems, half-integrality, primal-dual algorithms, supermodular functions, and many other concepts in combinatorial optimization. At the end of the tour, we may be left wondering: what's next?

Stephen Smith, CMU

Distributed Coordination of Mobile Agent Teams

We consider the problem of coordinating a team of agents engaged in executing a set of interdependent, geographically dispersed tasks in an oversubscribed and uncertain environment. In the distributed problem solving setting of interest, each agent is provided with an initial schedule of tasks to perform, and no agent has a global view of the problem. As execution unfolds and dynamics ensue (e.g., tasks fail, new tasks are discovered, etc.), agents must coordinate to extend and revise their schedules accordingly. The team objective is to maximize the cumulative utility accrued from executed actions over a given time horizon. For this class of dynamic problem, where the time that agents spend traveling reduces the amount of time available to execute quality accruing tasks, we argue that there is inherent leverage to having agents maintain advance schedules. We describe an approach to solving this problem based on distributed management of agent schedules. Experimental results obtained running in a closed loop with a world simulator are presented that show its dominance over an intelligent dispatching strategy previously shown to outperform our approach on synthetic, stateless utility maximization problems. Finally, we summarize performance results obtained with an extension of our approach on a limited set of field test experiments designed to mimic response to a natural disaster.