4 Presentations

• 
  10:30 AM - 10:55 AM

  Reconsidering Mixed Integer Programming, Constraint Programming, and MIP/CP Hybrids for Scheduling

  • J. Christopher Beck, presenter, University of Toronto
  • Stefan Heinz, Zuse Institute Berlin

  Despite the success of constraint programming (CP) for scheduling, the much wider penetration of mixed integer programming (MIP) technology into business applications means that many practical scheduling problems are being addressed with MIP, at least as an initial approach. Furthermore, there has been impressive and well-documented improvements in the power of generic MIP solvers over the past decade. We empirically demonstrate that on an existing set of resource allocation and scheduling problems standard MIP and CP models are now competitive with the state-of-the-art manual decomposition approach. Motivated by this result, we formulate two tightly coupled hybrid models based on constraint integer programming (CIP) and demonstrate that these models, which embody advances in CP and MIP, are able to out-perform the CP, MIP, and decomposition models. We conclude that both MIP and CIP are technologies that should be considered along with CP for solving scheduling problems?

• 
  10:55 AM - 11:20 AM

  MDD Propagation for Disjunctive Scheduling

  • Willem-Jan van Hoeve, presenter, Carnegie Mellon University
  • Andre A. Cire, Carnegie Mellon University

  Disjunctive scheduling is the problem of scheduling activities that must not overlap in time. Constraint-based techniques, such as edge finding and not-first/not-last rules, have been a key element in successfully tackling large and complex disjunctive scheduling problems in recent years. In this work we investigate new propagation methods based on limited-width Multivalued Decision Diagrams (MDDs). We present theoretical properties of the MDD encoding and describe filtering and refinement operations that strengthen the relaxation it provides. Furthermore, we provide an efficient way to integrate the MDD-based reasoning with state-of-the-art propagation techniques for scheduling. Experimental results indicate that the MDD propagation can outperform existing domain filters especially when minimizing sequence-dependent setup times, in certain cases by several orders of magnitude.

• 
  11:20 AM - 11:45 AM

  Scheduling a Batch Processing Machine with Constraints

  • Louis-Martin Rousseau, presenter, Polytechnique Montréal
  • Arnaud Malapert, Université de Nice
  • Christelle Guéret, École des Mines de Nantes

  This paper presents a constraint programming approach for a batch-processing machine on which a finite number of jobs of non-identical sizes must be scheduled. A parallel batch-processing machine can process several jobs simultaneously and the objective is to minimize the maximal lateness. The constraint programming formulation proposed relies on the decomposition of the problem into finding an assignment of the jobs to the batches, and then minimizing the lateness of the batches on a single machine. This formulation is enhanced by a new optimization constraint, which is based on a relaxed problem and applies cost-based domain filtering techniques. Experimental results demonstrate the efficiency of cost-based domain filtering techniques. Comparisons to other exact approaches clearly show the benefits of the proposed approach: it can optimally solve problems that are one order of magnitude greater than those solved by a mathematical formulation or by a branch-and-price.

• 
  11:45 AM - 12:10 PM

  Solving Two-Machine Assembly Scheduling Problems with Inventory Constraints

  • Daria Terekhov, presenter, University of Toronto
  • Mustafa K. Dogru, Alcatel-Lucent Bell Labs
  • Ulas Ozen, Alcatel-Lucent Bell Labs
  • J. Christopher Beck, University of Toronto

  We consider a scheduling problem with component availability constraints in a supply chain with two manufacturers and a merge-in-transit facility. Three mixed-integer programming models and a
  constraint programming model are compared in an extensive numerical study. Results show that
  performance is dependent on component types and magnitude of processing times.