Many sequencing and scheduling problems are too complex for mathematics.

Mathematical programming (MP) techniques based on linear algebra—the most common techniques used in optimization problems—break down on most large detailed scheduling and sequencing problems.

Fortunately, ILOG can help. As the leader in optimization, ILOG has developed a second optimization technology, called constraint programming (CP), aimed at solving these difficult scheduling and sequencing problems. Although math is used to help find the correct search path from several choices, ILOG's CP technology is based primarily on computer science fundamentals, such as logic programming and graph theory.

The CP approach to optimization is completely different than the MP approach. CP finds efficient solutions—feasible combinations and good assignments of resources and activities—when there are too many individual sequencing and timing constraints for MP. It then works to improve the solution until nothing better can be found.

CP is invaluable when dealing with the complexity of many real-world sequencing and scheduling problems. Whether you are scheduling people, machines or process steps, you need CP when there are too many operating constraints and individual business rules for solutions based on linear algebra.

ILOG's CP technology systematically eliminates possibilities in order to reduce the size of the "search space," rapidly identifying feasible solutions that can then be optimized. You can model your real scheduling and sequencing problems instead of simplifying them for an MP model.

Enlarge thumbnails (opens a new window).

Work with the same core elements as ILOG CPLEX
While a CP engine works differently than an MP engine such as ILOG CPLEX, ILOG's optimization tools allow you to model business problems in much the same way.

A CP model is expressed in a declarative fashion, using decision variables, constraints and objectives that must be minimized or maximized. And ILOG's modeling language and integrated development environment (IDE)—the ILOG OPL-CPLEX Development System—can now be used to write MP models, CP models, or both, working in harmony in a multi-model solution to a scheduling problem. With ILOG CP Optimizer, modelers' risks are reduced when using constraint programming compared to coding custom heuristics.

ILOG CP and ILOG CP Optimizer allow you work with the same core business objects and concepts used by ILOG CPLEX, such as:

• Production orders to be manufactured
• Orders to be loaded
• Deliveries and pick-ups to be scheduled
• Staff to be scheduled
• Resources that can be used
• Operating activities and costs associated with delivery
• Operating constraints and preferences
• Business policy rules
• Metrics (KPIs), for use when measuring and comparing solutions

The power of modeling in CP
Modeling in CP revolves around the details of what is possible. For example, if you have to schedule a large number of resources and activities that respect capacity limitations, operational sequencing requirements, and business policies while meeting individual customer service goals, you may need to:

• Define activities with information about execution time, sub-activities, resource requirements, allowed alternative resources, precedence requirements and costs
• Define resources with capacities, costs and capabilities that can be utilized, consumed or shared by certain activities and produced by others
• Balance conflicting business goals
• Keep track of resource utilization, consumption and available capacity
• Keep track of time to be able to sequence activities and respect time windows when activities must occur
• Control the allowed values for each decision variable
• Reduce the available values for a decision variable as other variables are determined

The following three concepts are fundamental to the way CP generates workable schedules from such complexity:

• Awareness of time
  While MP can divide time into buckets and decide what is "optimal" to do in each bucket, it does not do a good job of computing the optimal sequence of large numbers of inter-related activities with a start time for each. ILOG CP Optimizer can determine the best sequence of activities that satisfy capacity limitations, set-up times, maintenance requirements, availability restrictions, individual delivery due dates, and more. Simply put, ILOG CP Optimizer is better than ILOG CPLEX at handling time in detailed scheduling problems.
  
  
• Aggressive elimination of possibilities
  Domain reduction is the internal mechanism that makes difficult allocation, sequencing and scheduling problems manageable. Every resource or activity to be scheduled has a certain number of possible values that can be systematically reduced until a solution is reached. Every reduction makes the problem easier. Reducing the size of the search space is a concept fundamental to both MP and CP, but each engine goes about it differently. ILOG CP Optimizer has virtually no limits on their abilities to work with non-linear constraints.
  
  
• Rapidly traversing the decision tree
  The concept of systematically exploring a decision tree for feasible and efficient solutions relates to domain reduction. One benefit of this structured approach is the ability to move flexibly throughout the search space and to backtrack when early choices turn out to be dead ends. Like MP technology, ILOG's CP technology has focused a great deal on search strategies and manipulates large amounts of data in memory