(!******************************************************
Mosel Example Problems
======================
file sequencing.mos
```````````````````
TYPE: Sequencing jobs on a machine (single machine scheduling)
DIFFICULTY: 3
FEATURES: MIP problem with 3 different objectives; `procedure'
for solution printing, `if-then'
DESCRIPTION: A set of tasks (or jobs) is to be processed on a single
machine. The execution of tasks is non-preemptive (that is,
an operation may not be interrupted before its completion).
For every task its release date, due date, and duration are
given.
The model shows how to minimize the total processing time,
the average processing time, and the total tardiness (that
is, the amount of time by which the completion of jobs
exceeds their respective due dates).
FURTHER INFO: `Applications of optimization with Xpress-MP',
Section 7.4 `Sequencing jobs on a bottleneck machine'
(c) 2008 Fair Isaac Corporation
author: S. Heipcke, 2002, rev. Sep. 2017
*******************************************************!)
model "Sequencing"
uses "mmxprs", "mmsvg", "mmsystem"
forward procedure print_sol(obj:integer)
forward procedure draw_sol(obj:integer)
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,JOBS) of mpvar ! =1 if job j at position k
start: array(JOBS) of mpvar ! Start time of job at position k
comp: array(JOBS) of mpvar ! Completion time of job at position k
late: array(JOBS) of mpvar ! Lateness of job at position k
finish: mpvar ! Completion time of the entire schedule
end-declarations
initializations from 'sequencing.dat'
DUR REL DUE
end-initializations
! One job per position
forall(k in JOBS) OneJobPos(k):= sum(j in JOBS) rank(j,k) = 1
! One position per job
forall(j in JOBS) OnePosJob(j):= sum(k in JOBS) rank(j,k) = 1
! Sequence of jobs
forall(k in 1..NJ-1)
Prec(k):= start(k+1) >= start(k) + sum(j in JOBS) DUR(j)*rank(j,k)
! Start times
forall(k in JOBS) Start(k):= start(k) >= sum(j in JOBS) REL(j)*rank(j,k)
! Completion times
forall(k in JOBS)
Complete(k):= comp(k) = start(k) + sum(j in JOBS) DUR(j)*rank(j,k)
! Lateness
forall(k in JOBS)
Late(k):= late(k) >= comp(k) - sum(j in JOBS) DUE(j)*rank(j,k)
forall(j,k in JOBS) rank(j,k) is_binary
YFACT:=3
svgsetgraphviewbox(0,0,max(j in JOBS)DUE(j)+10, 12*YFACT)
svgsetgraphscale(10)
! Objective function 1: minimize latest completion time
forall(k in JOBS) Finish(k):= finish >= comp(k)
minimize(finish)
print_sol(1)
draw_sol(1)
! Objective function 2: minimize average completion time
minimize(sum(k in JOBS) comp(k))
print_sol(2)
draw_sol(2)
! Objective function 3: minimize total tardiness
minimize(sum(k in JOBS) late(k))
print_sol(3)
draw_sol(3)
svgwaitclose("Close browser window to terminate model execution.", 1)
!-----------------------------------------------------------------
! Solution printing
procedure print_sol(obj:integer)
writeln("Objective ", obj, ": ", getobjval,
if(obj>1, " completion time: " + getsol(finish), "") ,
if(obj<>2, " average: " + getsol(sum(k in JOBS) comp(k)), ""),
if(obj<>3, " lateness: " + getsol(sum(k in JOBS) late(k)), ""))
write(strfmt("",6))
forall(k in JOBS) write(strfmt(getsol(sum(j in JOBS) j*rank(j,k)),4))
write("\n",strfmt("Rel",-6))
forall(k in JOBS) write(strfmt(getsol(sum(j in JOBS) REL(j)*rank(j,k)),4))
write("\n",strfmt("Dur",-6))
forall(k in JOBS) write(strfmt(getsol(sum(j in JOBS) DUR(j)*rank(j,k)),4))
write("\n",strfmt("Start",-6))
forall(k in JOBS) write(strfmt(getsol(start(k)),4))
write("\n",strfmt("End",-6))
forall(k in JOBS) write(strfmt(getsol(comp(k)),4))
write("\n",strfmt("Due",-6))
forall(k in JOBS) write(strfmt(getsol(sum(j in JOBS) DUE(j)*rank(j,k)),4))
if(obj=3) then
write("\n",strfmt("Late",-6))
forall(k in JOBS) write(strfmt(getsol(late(k)),4))
end-if
writeln
end-procedure
!-----------------------------------------------------------------
! Solution drawing
procedure draw_sol(obj:integer)
if obj>1 and svgclosing then exit(0); end-if
! svgerase("msg")
if obj=1 then svgaddgroup("msg", "Objective", SVG_BLACK); end-if
svgaddtext("msg",0,YFACT*3*obj-1,formattext("Objective %d: %g %s%s%s", obj, getobjval,
if(obj>1, " completion time: " + getsol(finish), ""),
if(obj<>2, " average: " + getsol(sum(k in JOBS) comp(k)), ""),
if(obj<>3, " lateness: " + getsol(sum(k in JOBS) late(k)), "")))
forall(j in JOBS) do
pos:=round(getsol(sum(k in JOBS) k*rank(j,k)))
if obj=1 then
svgaddgroup("J"+j, "Job "+j)
svgsetstyle(SVG_FILL,SVG_CURRENT)
end-if
svgaddrectangle("J"+j, start(pos).sol,YFACT*3*obj,comp(pos).sol-start(pos).sol, YFACT)
end-do
svgrefresh
if obj<3 then svgpause; end-if
end-procedure
end-model
|
