Initializing help system before first use

Sequencing jobs on a bottleneck machine
Type: Sequencing
Rating: 2 (easy-medium)
Description: Sequencing jobs on a bottleneck machine: consecutive solving with 3 different objectives;
  • linear and 'element' constraints; branching strategy for variables (b4seq_ka.mos).
  • Alternative formulation using 'disjunctive' constraint, branching over variables and constraints (b4seq2_ka.mos).
  • Third formulation as disjunctive scheduling / sequencing problem, modeled with task and resource objects (b4seq3_ka.mos).
File(s): b4seq_ka.mos, b4seq2_ka.mos, b4seq3_ka.mos
Data file(s): b4seq.dat

b4seq_ka.mos
(!******************************************************
   CP Example Problems
   ===================

   file b4seq_ka.mos
   `````````````````
   Sequencing jobs on a bottleneck machine
   (See "Applications of optimization with Xpress-MP",
        Section 7.4 Sequencing jobs on a bottleneck machine)

   *** This model cannot be run with a Community Licence 
       for the provided data instance ***

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

model "B-4 Sequencing (CP)"
 uses "kalis"

 forward procedure print_sol
 forward procedure print_sol3
 
 declarations   
  NJ = 7                          ! Number of jobs
  JOBS=1..NJ

  REL: array(JOBS) of integer     ! Release dates of jobs
  DUR: array(JOBS) of integer     ! Durations of jobs
  DUE: array(JOBS) of integer     ! Due dates of jobs

  rank: array(JOBS) of cpvar      ! Number of job at position k
  start: array(JOBS) of cpvar     ! Start time of job at position k
  dur: array(JOBS) of cpvar       ! Duration of job at position k
  comp: array(JOBS) of cpvar      ! Completion time of job at position k
  rel: array(JOBS) of cpvar       ! Release date of job at position k
 end-declarations
 
 initializations from 'Data/b4seq.dat'
  DUR REL DUE
 end-initializations

 MAXTIME:= max(j in JOBS) REL(j) + sum(j in JOBS) DUR(j)
 MINDUR:= min(j in JOBS) DUR(j); MAXDUR:= max(j in JOBS) DUR(j)
 MINREL:= min(j in JOBS) REL(j); MAXREL:= max(j in JOBS) REL(j)

 forall(j in JOBS) do
  1 <= rank(j); rank(j) <= NJ
  0 <= start(j); start(j) <= MAXTIME 
  MINDUR <= dur(j); dur(j) <= MAXDUR
  0 <= comp(j); comp(j) <= MAXTIME
  MINREL <= rel(j); rel(j) <= MAXREL
 end-do 

! One posistion per job
 all_different(rank)

! Duration of job at position k
 forall(k in JOBS) dur(k) = element(DUR, rank(k))

! Release date of job at position k
 forall(k in JOBS) rel(k) = element(REL, rank(k))
 
! Sequence of jobs
 forall(k in 1..NJ-1) start(k+1) >= start(k) + dur(k)

! Start times
 forall(k in JOBS) start(k) >= rel(k)

! Completion times
 forall(k in JOBS) comp(k) = start(k) + dur(k)

! Set the branching strategy
 cp_set_branching(split_domain(KALIS_SMALLEST_DOMAIN, KALIS_MIN_TO_MAX))

!**** Objective function 1: minimize latest completion time ****
 if cp_minimize(comp(NJ)) then
  print_sol
 end-if


!**** Objective function 2: minimize average completion time ****
 declarations   
  totComp: cpvar
 end-declarations
 
 totComp = sum(k in JOBS) comp(k)

 if cp_minimize(totComp) then
  print_sol
 end-if


!**** Objective function 3: minimize total tardiness ****
 declarations   
  late: array(JOBS) of cpvar      ! Lateness of job at position k
  due: array(JOBS) of cpvar       ! Due date of job at position k
  totLate: cpvar
 end-declarations

 MINDUE:= min(k in JOBS) DUE(k); MAXDUE:= max(k in JOBS) DUE(k)

 forall(k in JOBS) do
  MINDUE <= due(k); due(k) <= MAXDUE
  0 <= late(k); late(k) <= MAXTIME
 end-do 

! Due date of job at position k
 forall(k in JOBS) due(k) = element(DUE, rank(k))
 
! Late jobs: completion time exceeds the due date
 forall(k in JOBS) late(k) >= comp(k) - due(k) 

 totLate = sum(k in JOBS) late(k)

 if cp_minimize(totLate) then
  writeln("Tardiness: ", getsol(totLate))
  print_sol
  print_sol3
 end-if

!-----------------------------------------------------------------

! Solution printing
 procedure print_sol   
  writeln("Completion time: ", getsol(comp(NJ)) ,
          "  average: ", getsol(sum(k in JOBS) comp(k)))
  write("\t")
  forall(k in JOBS) write(strfmt(getsol(rank(k)),4))
  write("\nRel\t")
  forall(k in JOBS) write(strfmt(getsol(rel(k)),4))
  write("\nDur\t")
  forall(k in JOBS) write(strfmt(getsol(dur(k)),4))
  write("\nStart\t")
  forall(k in JOBS) write(strfmt(getsol(start(k)),4))
  write("\nEnd\t")
  forall(k in JOBS) write(strfmt(getsol(comp(k)),4))
  writeln
 end-procedure

 procedure print_sol3
  write("Due\t")
  forall(k in JOBS) write(strfmt(getsol(due(k)),4))
  write("\nLate\t")
  forall(k in JOBS) write(strfmt(getsol(late(k)),4))
  writeln
 end-procedure 
 
end-model
b4seq2_ka.mos
(!******************************************************
   CP Example Problems
   ===================

   file b4seq2_ka.mos
   ``````````````````
   Sequencing jobs on a bottleneck machine
   (See "Applications of optimization with Xpress-MP",
        Section 7.4 Sequencing jobs on a bottleneck machine)
   - Alternative formulation using disjunctions -

   *** This model cannot be run with a Community Licence 
       for the provided data instance ***

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

model "B-4 Sequencing (CP)"
 uses "kalis"

 forward procedure print_sol
 forward procedure print_sol3
 
 declarations   
  NJ = 7                          ! Number of jobs
  JOBS=1..NJ

  REL: array(JOBS) of integer     ! Release dates of jobs
  DUR: array(JOBS) of integer     ! Durations of jobs
  DUE: array(JOBS) of integer     ! Due dates of jobs
  DURS: array(set of cpvar) of integer  ! Dur.s indexed by start variables

  start: array(JOBS) of cpvar     ! Start time of jobs
  comp: array(JOBS) of cpvar      ! Completion time of jobs
  finish: cpvar                   ! Completion time of the entire schedule
  Disj: set of cpctr              ! Disjunction constraints 
  Strategy: array(range) of cpbranching  ! Branching strategy
 end-declarations
 
 initializations from 'Data/b4seq.dat'
  DUR REL DUE
 end-initializations

 MAXTIME:= max(j in JOBS) REL(j) + sum(j in JOBS) DUR(j)

 forall(j in JOBS) do
  0 <= start(j); start(j) <= MAXTIME 
  0 <= comp(j); comp(j) <= MAXTIME
 end-do 

! Disjunctions between jobs
 forall(j in JOBS) DURS(start(j)):= DUR(j)
 disjunctive(union(j in JOBS) {start(j)}, DURS, Disj, 1)

! Start times
 forall(j in JOBS) start(j) >= REL(j)

! Completion times
 forall(j in JOBS) comp(j) = start(j) + DUR(j)

!**** Objective function 1: minimize latest completion time ****
 finish = maximum(comp)

 Strategy(1):= settle_disjunction(Disj)
 Strategy(2):= split_domain(KALIS_LARGEST_MAX, KALIS_MIN_TO_MAX)
 cp_set_branching(Strategy)
 
 if cp_minimize(finish) then
  print_sol
 end-if


!**** Objective function 2: minimize average completion time ****
 declarations   
  totComp: cpvar
 end-declarations

 totComp = sum(k in JOBS) comp(k)

 if cp_minimize(totComp) then
  print_sol
 end-if


!**** Objective function 3: minimize total tardiness ****
 declarations   
  late: array(JOBS) of cpvar      ! Lateness of jobs
  totLate: cpvar
 end-declarations

 forall(k in JOBS) do
  0 <= late(k); late(k) <= MAXTIME
 end-do 
 
! Late jobs: completion time exceeds the due date
 forall(j in JOBS) late(j) >= comp(j) - DUE(j) 

 totLate = sum(k in JOBS) late(k)
 if cp_minimize(totLate) then
  writeln("Tardiness: ", getsol(totLate))
  print_sol
  print_sol3
 end-if

!-----------------------------------------------------------------

! Solution printing
 procedure print_sol
  writeln("Completion time: ", getsol(finish) ,
          "  average: ", getsol(sum(j in JOBS) comp(j)))
  write("Rel\t")
  forall(j in JOBS) write(strfmt(REL(j),4))
  write("\nDur\t")
  forall(j in JOBS) write(strfmt(DUR(j),4))
  write("\nStart\t")
  forall(j in JOBS) write(strfmt(getsol(start(j)),4))
  write("\nEnd\t")
  forall(j in JOBS) write(strfmt(getsol(comp(j)),4))
  writeln
 end-procedure

 procedure print_sol3
  write("Due\t")
  forall(j in JOBS) write(strfmt(DUE(j),4))
  write("\nLate\t")
  forall(j in JOBS) write(strfmt(getsol(late(j)),4))
  writeln
 end-procedure 
 
end-model
b4seq3_ka.mos
(!******************************************************
   CP Example Problems
   ===================

   file b4seq3_ka.mos
   ``````````````````
   Sequencing jobs on a bottleneck machine
   - Alternative formulation using disjunctions
     between tasks -
   
   *** This model cannot be run with a Community Licence 
       for the provided data instance ***

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

model "B-4 Sequencing (CP)"
 uses "kalis"

 forward procedure print_sol
 forward procedure print_sol3
 
 declarations   
  NJ = 7                          ! Number of jobs
  JOBS=1..NJ

  REL: array(JOBS) of integer     ! Release dates of jobs
  DUR: array(JOBS) of integer     ! Durations of jobs
  DUE: array(JOBS) of integer     ! Due dates of jobs

  task: array(JOBS) of cptask     ! Tasks (jobs to be scheduled)
  res: cpresource                 ! Resource (machine)

  finish: cpvar                   ! Completion time of the entire schedule
 end-declarations
 
 initializations from 'Data/b4seq.dat'
  DUR REL DUE
 end-initializations
 
! Setting up the resource (formulation of the disjunction of tasks)
 set_resource_attributes(res, KALIS_UNARY_RESOURCE, 1)
 
! Setting up the tasks (durations and disjunctions)
 forall(j in JOBS) set_task_attributes(task(j), DUR(j), res)
 
 MAXTIME:= max(j in JOBS) REL(j) + sum(j in JOBS) DUR(j)

 forall(j in JOBS) do
  0 <= getstart(task(j)); getstart(task(j)) <= MAXTIME 
  0 <= getend(task(j)); getend(task(j)) <= MAXTIME
 end-do 

! Start times
 forall(j in JOBS) getstart(task(j)) >= REL(j)

!**** Objective function 1: minimize latest completion time ****
 declarations
  L: cpvarlist
 end-declarations
 
 forall(j in JOBS) L += getend(task(j))
 finish = maximum(L)

 if cp_schedule(finish) >0 then
  print_sol
 end-if


!**** Objective function 2: minimize average completion time ****
 declarations   
  totComp: cpvar
 end-declarations

 totComp = sum(j in JOBS) getend(task(j))

 if cp_schedule(totComp) > 0 then
  print_sol
 end-if


!**** Objective function 3: minimize total tardiness ****
 declarations   
  late: array(JOBS) of cpvar      ! Lateness of jobs
  totLate: cpvar
 end-declarations

 forall(j in JOBS) do
  0 <= late(j); late(j) <= MAXTIME
 end-do 
 
! Late jobs: completion time exceeds the due date
 forall(j in JOBS) late(j) >= getend(task(j)) - DUE(j) 

 totLate = sum(j in JOBS) late(j)
 if cp_schedule(totLate) > 0 then
  writeln("Tardiness: ", getsol(totLate))
  print_sol
  print_sol3
 end-if


!-----------------------------------------------------------------

! Solution printing
 procedure print_sol
  writeln("Completion time: ", getsol(finish) ,
          "  average: ", getsol(sum(j in JOBS) getend(task(j))))
  write("Rel\t")
  forall(j in JOBS) write(strfmt(REL(j),4))
  write("\nDur\t")
  forall(j in JOBS) write(strfmt(DUR(j),4))
  write("\nStart\t")
  forall(j in JOBS) write(strfmt(getsol(getstart(task(j))),4))
  write("\nEnd\t")
  forall(j in JOBS) write(strfmt(getsol(getend(task(j))),4))
  writeln
 end-procedure

 procedure print_sol3
  write("Due\t")
  forall(j in JOBS) write(strfmt(DUE(j),4))
  write("\nLate\t")
  forall(j in JOBS) write(strfmt(getsol(late(j)),4))
  writeln
 end-procedure 
 
end-model
Parent Topic Examples described in the Xpress Kalis User Guide

© 2001-2020 Fair Isaac Corporation. All rights reserved. This documentation is the property of Fair Isaac Corporation (“FICO”). Receipt or possession of this documentation does not convey rights to disclose, reproduce, make derivative works, use, or allow others to use it except solely for internal evaluation purposes to determine whether to purchase a license to the software described in this documentation, or as otherwise set forth in a written software license agreement between you and FICO (or a FICO affiliate). Use of this documentation and the software described in it must conform strictly to the foregoing permitted uses, and no other use is permitted.