disjunctive

Purpose

This constraint states that the given tasks are not overlapping chronologically.

Synopsis

procedure disjunctive(starts: set of cpvar, durations:array(cpvar) of integer, disj:set of cpctr, resource:integer)

procedure disjunctive(starts: array(integer) of cpvar, durations:array(integer) of cpvar, ends: array(integer) of cpvar)

Arguments

starts	Array of variables representing the start times of the tasks
durations	Array of integers representing the durations of the tasks
ends	Array of variables representing the completion times of the tasks
disj	Empty array that will be filled with the list of disjunctions that will be created by this constraint
resource	Resource flag (argument currently unused)

Return value

A disjunctive constraint ensuring that the tasks defined by 'starts' and 'durations' are not overlapping chronologically.

Example

The following example shows how to use the disjunctive constraint to express resource constraints in a small disjunctive scheduling problem:

model "Disjunctive scheduling with settle_disjunction"
 uses "kalis", "mmsystem"

 declarations
  NBTASKS = 5
  TASKS = 1..NBTASKS                     ! Set of tasks
  DUR: array(TASKS) of integer           ! Task durations
  DURs: array(set of cpvar) of integer   ! Durations
  DUE: array(TASKS) of integer           ! Due dates
  WEIGHT: array(TASKS) of integer        ! Weights of tasks
  start: array(TASKS) of cpvar           ! Start times
  tmp: array(TASKS) of cpvar             ! Aux. variable
  tardiness: array(TASKS) of cpvar       ! Tardiness
  twt: cpvar                             ! Objective variable
  zeroVar: cpvar                         ! 0-valued variable
  Strategy: array(range) of cpbranching  ! Branching strategy
  Disj: set of cpctr                     ! Disjunctions
 end-declarations

 DUR :: [21,53,95,55,34]
 DUE :: [66,101,232,125,150]
 WEIGHT :: [1,1,1,1,1]

 setname(twt, "Total weighted tardiness")
 zeroVar = 0
 setname(zeroVar, "zeroVar")

! Setting up the decision variables
 forall(t in TASKS) do
  start(t) >= 0
  setname(start(t), "Start("+t+")")
  DURs(start(t)):= DUR(t)
  tmp(t) = start(t) + DUR(t) - DUE(t)
  setname(tardiness(t), "Tard("+t+")")
  tardiness(t) = maximum({tmp(t), zeroVar})
 end-do

 twt = sum(t in TASKS) (WEIGHT(t) * tardiness(t))

! Create the disjunctive constraints
 disjunctive(union(t in TASKS) {start(t)}, DURs, Disj, 1)

! Define the search strategy
 Strategy(1):= settle_disjunction
 Strategy(2):= split_domain(KALIS_LARGEST_MIN,KALIS_MIN_TO_MAX)
 cp_set_branching(Strategy)
 setparam("KALIS_DICHOTOMIC_OBJ_SEARCH",true)

 if not cp_minimize(twt) then
  writeln("Problem is inconsistent")
  exit(0)
 end-if

 forall(t in TASKS)
  writeln(formattext("[%3d==>%3d]:\t %2d  (%d)", start(t).sol,
          start(t).sol + DUR(t), tardiness(t).sol, tmp(t).sol))
 writeln("Total weighted tardiness: ", getsol(twt))

end-model

Contents

Index

Glossary

Search Results

disjunctive