'cumulative' and 'disjunctive' constraints for scheduling and planning problems

• cumulative.mos: using the 'cumulative' constraint to formulate a scheduling problem with resource constraints (renewable resource with discrete capacity)
• disjunctive.mos: using the 'disjunctive' constraint for implementing a sequencing problem (single-maching scheduling minimizing the total weighted tardiness.
• resource_capacity.mos: using 'task' and 'resource' objects to model a cumulative resource relation (renewable resource with different capacity levels over time).
• resource_coupled_setup_times.mos: specifying setup times between pairs of tasks assigned to the same resource.

(!****************************************************************
   CP example problems
   ===================
   
   file cumulative.mos
   ```````````````````
   Cumulative scheduling example

   (c) 2008 Artelys S.A. and Fair Isaac Corporation

*****************************************************************!)

model "Cumulative scheduling"  
 uses "kalis"
 
 declarations 
  TASKS = 1..5
  obj : cpvar
  starts, ends, durations, usages, sizes : array(TASKS) of cpvar      
 end-declarations

 C := 2                       ! Resource capacity
 HORIZON := 10                ! Time horizon

! Setting up the variables representing task properties
 forall (t in TASKS) do 
  starts(t).name:= "T"+t+".start"
  ends(t).name:= "T"+t+".end"
  durations(t).name:= "T"+t+".duration"
  sizes(t).name:= "T"+t+".size"
  usages(t).name:= "T"+t+".use"
  0 <= starts(t); starts(t) <= HORIZON
  0 <= ends(t); ends(t) <= HORIZON
  t <= durations(t); durations(t) <= t+1
  1 <= sizes(t); sizes(t) <= 100
  1 <= usages(t); usages(t) <= 1
  obj >= ends(t)  
 end-do

! Cumulative resource constraint
 cumulative(starts, durations, ends, usages, sizes, C)

! Define the branching strategy
 cp_set_branching(assign_var(KALIS_SMALLEST_MIN,KALIS_MIN_TO_MAX))

! Solve the problem 
 if cp_minimize(obj) then 
  cp_show_sol 
  write("Resource use profile: ")
  forall(t in TASKS, time in 0..HORIZON)
   if (starts(t).sol <= time) and (ends(t).sol > time) then
    rload(time) += usages(t).sol
   end-if
  forall(time in 0..HORIZON) write(rload(time))  
  writeln
 else
  writeln("No solution found") 
 end-if

end-model

(!****************************************************************
   CP example problems
   ===================
   
   file disjunctive.mos
   ````````````````````
   Scheduling disjunctive tasks.

   (c) 2008 Artelys S.A. and Fair Isaac Corporation
       Creation: 2005, rev. 2007, rev. Mar. 2013
*****************************************************************!)
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

(!****************************************************************
   CP example problems
   ===================
   
   file resource_capacity.mos
   ``````````````````````````
   Setting capacity of a resource over time

   (c) 2008 Artelys S.A. and Fair Isaac Corporation

*****************************************************************!)
model "Resource capacity"  
 uses "kalis"
 
 declarations  
  A, B, C : cptask            ! Declaration of tasks
  resource : cpresource       ! Declaration of resource
 end-declarations

 setname(A,"A"); setname(B,"B"); setname(C,"C")

! The resource is a cumulative resource with maximum capacity 6
 set_resource_attributes(resource, KALIS_DISCRETE_RESOURCE, 6)

! Setting the resource capacity in the interval 0..2 to 3
 setcapacity(resource, 0, 2, 3)
! Setting the resource capacity in the interval 3..4 to 2
 setcapacity(resource, 3, 4, 2)
! Setting the resource capacity in time period 5 to 1
 setcapacity(resource, 5, 5, 1)

! Setting the task durations
 set_task_attributes(A, 1) 
 set_task_attributes(B, 2)
 set_task_attributes(C, 3)

! Setting the resource requirements of the tasks
 requires(A, 1, resource)
 requires(B, 2, resource)
 requires(C, 3, resource)
 
! Find the optimal schedule (minimizing the makespan)
 if cp_schedule(getmakespan) <> 0 then	
  cp_show_sol
 else
  writeln("no solution found") 		
 end-if

end-model

(!******************************************************
   CP example problems
   ===================
   
   file resource_coupled_setup_times.mos
   `````````````````````````````````````
   Resource-dependent setup times between two tasks.

   r.assign(t1) and r.assign(t2) => t1.end + setupt1t2 <= t2.start or
                                    t2.end + setupt2t1 <= t1.start

   Copyright(C) 2019 Artelys S.A. and Fair Isaac Corporation
                     Creation: 2019
*******************************************************!)

model "Resource coupled setup time"
 uses "kalis"

 declarations
  r: cpresource
  t1, t2, t3, t4, t5, t6: cptask
 end-declarations

! Resource and task configuration
 set_resource_attributes(r, KALIS_DISCRETE_RESOURCE, 4, KALIS_TIMETABLING)
 L:=[t1, t2, t3, t4, t5, t6]
 forall(t in L, ct as counter) do
   setname(t, "t"+ct)
   setduration(t, 20)
   requires(t, 1, r)
 end-do

! Resource-dependent setup times
 Dur1to2 := 11
 Dur2to1 := 6
 setsetuptime(r, t1, t2, Dur1to2, Dur2to1)

! Change (overwrite) setup time values
 setsetuptime(r, t3, t4, 10, 5)
 Dur3to4 := 1
 Dur4to3 := 5
 setsetuptime(r, t3, t4, Dur3to4, Dur4to3)

! No setup times between a pair of tasks
 setsetuptime(r, t5, t6, 0, 0)

 cp_close_schedule
 if cp_schedule(getmakespan) = 0 then
  writeln("Inconsistent schedule")
 end-if

 forall(t in L) writeln(t.name, " starts at: ", getsol(getstart(t)))

 if getsol(getstart(t5)) = getsol(getstart(t6)) then
  writeln("No setup time between t5 and t6")
 end-if

 cp_show_sol

end-model