(!******************************************************
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)
(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
|
(!******************************************************
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 -
(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
|
(!******************************************************
CP Example Problems
===================
file b4seq3_ka.mos
``````````````````
Sequencing jobs on a bottleneck machine
- Alternative formulation using disjunctions
between tasks -
(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
|
