Reasoning with Conditional Time-Intervals. Part II: An Algebraical Model for Resources

AAAI Conferences

In version 2.0, IBM ILOG CP Optimizer has been extended by the introduction of scheduling support based on the concept of optional interval variables. This paper formally describes the new modeling language features available to the users of CP Optimizer for resource-based scheduling. We show that the new language is flexible enough to model problems never before addressed by CP scheduling engines, as well as naturally describing classical scheduling problems found in the literature. This modeling power is based on a small number of general concepts such as intervals, sequences and functions. This makes the modeling language simple, clear and easy to learn, while maintaining the high-level structural aspects of the scheduling model.


New Results for the GEO-CAPE Observation Scheduling Problem

AAAI Conferences

A challenging Earth-observing satellite scheduling problem was recently studied in (Frank, Do and Tran 2016) for which the best resolution approach so far on the proposed benchmark is a time-indexed Mixed Integer Linear Program (MILP) formulation. This MILP formulation produces feasible solutions but is not able to prove optimality or to provide tight optimality gaps, making it difficult to assess the quality of existing solutions. In this paper, we first introduce an alternative disjunctive MILP formulation that manages to close more than half of the instances of the benchmark. This MILP formulation is then relaxed to provide good bounds on optimal values for the unsolved instances. We then propose a CP Optimizer model that consistently outperforms the original time-indexed MILP formulation, reducing the optimality gap by more than 4 times. This Constraint Programming (CP) formulation is very concise: we give its complete OPL implementation in the paper. Some improvements of this CP model are reported resulting in an approach that produces optimal or near-optimal solutions (optimality gap smaller than 1%) for about 80% of the instances. Unlike the MILP formulations, it is able to quickly produce good quality schedules and it is expected to be flexible enough to handle the changing requirements of the application.


Solving Scheduling Problems with Setup Times and Alternative Resources

AAAI Conferences

Two cooperative models for the problem based on Constraint Programming arc proposed. The first is used to model the scheduling constraints, while the second is a muhipath model used for setup optimization. Integrating lower bounding techniques for the sum of setup times, the multi-path model perforins propagation based on reduced cost fixing. A solution method based on a two phase algorithm is described,,'rod a computationM study is performed both on instances known from literature as on newly proposed instances. It is shown that the cooperation of the two modelsignificantly improves performance.


A Reformulation for the Problem of Scheduling Unrelated Parallel Machines with Sequence and Machine Dependent Setup Times

AAAI Conferences

In this paper we propose an improved formulation for an unrelated parallel machine problem with machine and job sequence-dependent setup times that outperforms the previously published formulations regarding size of instances and CPU time to reach optimal solutions. The main difference between the proposed formulation and previous ones is the way the makespan has been linearized. It provides improved dual bounds which speeds up the solution process when using a branch-and-bound commercial solver. Computational experiments show that, using this model, it is possible to solve instances four times larger than what was previously possible using other mixed integer programming formulations in the literature and obtain optimal solutions on instances of the same size up to three orders of magnitude faster.


Reasoning with Conditional Time-intervals

AAAI Conferences

Reasoning with conditional time-intervals representing activities or tasks that may or may not be executed in the final schedule is crucial in many scheduling applications. In Constraint-Based Scheduling, those problems are usually handled by defining new global constraints over classical integer variables. The approach described in this paper takes a different perspective by introducing a new type of variable (namely a time-interval variable) that intrinsically embeds the notion of conditionality.