settle_disjunction

Purpose

Creates a settle_disjunction branching scheme that resolves the status of all the disjunctions passed in argument. The branching consists in choosing one branch of the disjunction and posting the constraint stated by this branch. The branches are tested from left to right
BranchingSchemes/SettleDisjunction.png

Synopsis

function settle_disjunction(constraints: set of cpctr): cpbranching

function settle_disjunction(constraints: array(range) of cpctr): cpbranching

function settle_disjunction: cpbranching

function settle_disjunction(disjsel: function or string, constraints: set of cpctr): cpbranching

function settle_disjunction(disjsel: function or string, array(range) of cpctr): cpbranching

function settle_disjunction(disjsel: function or string): cpbranching

Arguments

constraints	the disjunctions
disjsel	a disjunction selection function

Return value

The resulting settle_disjunction branching scheme

Example

The following example shows how to use the settle_disjunction branching scheme to solve a small disjunctive scheduling problem: The problem is to find a schedule for a set of tasks on one machine. The machine can process only one task at the time and the goal is to minimize the total weighted tardiness of the schedule.

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
  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")

 forall (t in TASKS) do
  start(t) >= 0
  setname(start(t), "Start("+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
 forall(t in 1..NBTASKS-1, s in t+1..NBTASKS)
  (start(t) + DUR(t) <= start(s)) or
  (start(s) + DUR(s) <= start(t))

 ! Define the branching strategy
 Strategy(1):= settle_disjunction
 Strategy(2):= split_domain(KALIS_LARGEST_MIN,KALIS_MIN_TO_MAX)
 cp_set_branching(Strategy)

 ! Solve the problem
 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

settle_disjunction