Scheduling examples

Provides examples of how some scheduling problems are solved using CP Optimizer.

Bridge construction

The problem is to schedule the construction of a five-segment bridge.

To access this example, go to: examples/opl/sched_bridge.

Bridge construction with resource breaks

This is a basic problem that involves building a house; the masonry, roofing, painting, etc. must be scheduled. Some tasks must necessarily take place before others, and these requirements are expressed through precedence constraints.

To access this example, go to: examples/opl/sched_bridgebr.

House building introductory problem

This is a basic problem that involves building a house; the masonry, roofing, painting, etc. must be scheduled. Some tasks must necessarily take place before others, and these requirements are expressed through precedence constraints.

To access this example, go to: examples/opl/sched_intro.

House building with budget and worker pools

This is a problem of building five houses in different locations; the masonry, roofing, painting, etc. must be scheduled. Some tasks must necessarily take place before others and these requirements are expressed through precedence constraints.

There are three workers, and each task requires a worker. There is also a cash budget which starts with a given balance. Each task costs a given amount of cash per day which must be available at the start of the task. At the end of the moving task, a payment is received. The objective is to minimize the overall completion date.

To access this example, go to: examples/opl/sched_cumul. This example illustrates the use of IloCumulFunctionExpr .

See also Using cumulative functions in the house building problem in Getting Started with Scheduling in CPLEX Studio, where this problem is discussed in more detail.

House building with earliness/tardiness costs

This is a problem of building a house; the masonry, roofing, painting, etc. must be scheduled. Some tasks must necessarily take place before others and these requirements are expressed through precedence constraints.

Moreover, there are earliness and tardiness costs associated with some tasks. The objective is to minimize these costs.

To access this example, go to: examples/opl/sched_time.

See also the Modeling and Solving a Simple Problem: House Building section of the Language User's Manual, where this problem is discussed in more detail.

House building with resource calendars

This is a problem of building five houses in different locations; the masonry, roofing, painting, and so forth. Some tasks must necessarily take place before others and these requirements are expressed through precedence subject to.

There are two workers and each task requires a specific worker. The worker has a calendar of days off that must be taken into account. The objective is to minimize the overall completion date.

To access this example, go to: examples/opl/sched_calendar.

See also the Adding Calendars to the House Building Problem section of the Language User's Manual, where this problem is discussed in more detail.

House building with state incompatibilities

This is a problem of scheduling the tasks involved in building multiple houses. Some tasks must necessarily take place before other tasks, and each task has a predefined size. Moreover, there are two workers, and each task requires either one of the two workers.

A subset of the tasks require that the house be clean, whereas other tasks make the house dirty. A transition time is needed to change the state of the house from dirty to clean.

The problem consists of assigning start dates to a set of tasks in such a way that the schedule satisfies temporal constraints and minimizes a criterion. The criterion for this problem is to minimize the overall completion date.

To access this example, go to: examples/opl/sched_state.

House building with two workers

This is a problem of building five houses in different locations; the masonry, roofing, painting, etc. must be scheduled. Some tasks must necessarily take place before others and these requirements are expressed through precedence constraints.

There are two workers, and each task requires a specific worker. The time required for the workers to travel between houses must be taken into account.

Moreover, there are tardiness costs associated with some tasks as well as a cost associated with the length of time it takes to build each house. The objective is to minimize these costs.

To access this example, go to: examples/opl/sched_sequence.

See also the Adding Workers and Transition Times to the House Building Problem section of the Language User's Manual, where this problem is discussed in more detail.

House building with worker skills

This is a problem of building five houses in different locations; the masonry, roofing, painting, etc. must be scheduled. Some tasks must necessarily take place before others and these requirements are expressed through precedence constraints.

There are three workers, and each worker has a given skill level for each task. Each task requires one worker; the worker assigned must have a non-null skill level for the task. A worker can be assigned to only one task at a time.

Each house has a deadline. The objective is to maximize the skill levels of the workers assigned to the tasks.

To access this example, go to: examples/opl/sched_optional.

See also the Using Alternative Resources in the House Building Problem section of the Language User's Manual, where this problem is discussed in more detail.

Multi-mode resource-constrained project scheduling

The MMRCPSP problem is a generalization of the Resource-Constrained Project Scheduling problem. In the MMRCPSP, each activity can be performed in one out of several modes. Each mode of an activity represents an alternative way of combining different levels of resource requirements with a related duration. Renewable and no-renewable resources are distinguished. While renewable resources have a limited instantaneous availability such as manpower and machines, non renewable resources are limited for the entire project, allowing to model, e.g., a budget for the project.

The objective is to find a mode and a start time for each activity such that the schedule is makespan minimal and feasible with regard to the precedence and resource constraints.

To access this example, go to: examples/opl/sched_rcpspmm.

Open-shop scheduling problem

This problem can be described as follows: a finite set of operations has to be processed on a given set of machines. Each operation has a specific processing time during which it may not be interrupted. Operations are grouped in jobs, so that each operation belongs to exactly one job. Furthermore, each operation requires exactly one machine for processing.

The objective of the problem is to schedule all operations, i.e., to determine their start time, so as to minimize the maximum completion time (makespan) given the additional constraints that: operations which belong to the same job and operations which use the same machine cannot be processed simultaneously.

To access this example, go to: examples/opl/sched_openshop.

Production scheduling

A chemical manufacturer produces batches of specialty chemicals to order. An order consists of a set of jobs. Each job has an optional precedence requirement, arrival week of the job, duration of the job in weeks, the week that the job is due, the number of reactors required, distillation columns required, and centrifuges required. The objective is to minimize the completion time of all orders.

To access this example, go to: examples/opl/sched_production.

Resource allocation for house building

The problem consists of allocating workers to a set of house building tasks whose start and end time is already fixed.

To access this example, go to: examples/opl/sched_alloc.

Resource-constrained project scheduling problem

The RCPSP problem is a generalization of the production-specific Job-Shop, Flow-Shop and Open-Shop scheduling problems. Given

  • a set of resources with given capacities

  • a network of precedence constraints between the activities

  • for each activity and each resource, the amount of the resource required by the activity over its execution

the goal of the RCPSP problem is to find a schedule meeting all the constraints whose makespan (i.e., the time at which all activities are finished) is minimal.

To access this example, go to: examples/opl/sched_rcpsp.

Ship loading

The problem consists of scheduling the loading of a ship.

To access this example, go to: examples/opl/sched_shipload.

Shop scheduling with trolley I

This problem involves scheduling activities in a production shop where a trolley is used to carry items to the various machines.

To access this example, go to: examples/opl/sched_trolley1.

Shop scheduling with trolley II

This problem consists of scheduling activities in a production shop where a trolley is used to carry items to the various machines. This version of the problem takes into account the time taken by the trolley to go from one area to another.

To access this example, go to: examples/opl/sched_trolley2.

Square problem

The aim of the square example is to place a set of small squares of different sizes into a large square.

To access this example, go to: examples/opl/sched_square.

The basic job-shop scheduling problem

In this problem a finite set of jobs is processed on a finite set of machines. Each job is characterized by a fixed order of operations, each of which is to be processed on a specific machine for a specified duration.

Each machine can process at most one job at a time and once a job initiates processing on a given machine it must complete processing uninterrupted.

The objective of the problem is to find a schedule that minimizes the makespan of the jobs.

To access this example, go to: examples/opl/sched_jobshop.

The flexible job-shop scheduling

This problem is an extension of the classical Job-Shop Scheduling problem which allows an operation to be processed by any machine from a given set. The problem is to assign each operation to a machine and to order the operations on the machines such that the maximal completion time (makespan) of all operations is minimized.

To access this example, go to: examples/opl/sched_jobshopflex.

The flow-shop scheduling problem

This problem is a special case of Job-Shop Scheduling problem for which all jobs have the same processing order on machines because there is a technological order on the machines for the different jobs to follow.

To access this example, go to: examples/opl/sched_flowshop.

Transition based scheduling

Three OPL models are provided as examples of transition based scheduling. They can be found in your installation directory:

<Install_dir>/opl/examples/opl

  • examples/opl/sched_pflowshop — a permutation flow-shop problem.

  • examples/opl/sched_setup — calculates transition times between immediate successors and forbidden transitions in a sequence.

  • examples/opl/sched_tcost — minimizes the total transition cost.

C++ versions of these examples are described in the CP Optimizer documentation.