| |||||||||

Job shop scheduling Description A company has received an order for three types of
wallpapers. Every paper type is produced as a continuous
roll of paper that passes through several machines, each
printing a different color. The order in which the papers
are run through the machines depends on the design of the
paper. The processing times differ depending on the surface
that needs to be printed.
Knowing that every machine can only process one wallpaper
at a time and that a paper cannot be processed by several
machines simultaneously, how should the paper printing be
scheduled on the machines in order to finish the order as
early as possible? Further explanation of this example:
'Applications of optimization with Xpress-MP',
Section 7.3 'Job shop scheduling'
Source Files Data Files jobshop_graph.mos (!****************************************************** Mosel Example Problems ====================== file jobshop.mos ```````````````` TYPE: Job shop scheduling problem DIFFICULTY: 3 FEATURES: MIP problem, formulating disjunctions (BigM); `dynamic array', `range', `exists', `forall-do', graphical solution representation DESCRIPTION: A company has received an order for three types of wallpapers. Every paper type is produced as a continuous roll of paper that passes through several machines, each printing a different color. The order in which the papers are run through the machines depends on the design of the paper. The processing times differ depending on the surface that needs to be printed. Knowing that every machine can only process one wallpaper at a time and that a paper cannot be processed by several machines simultaneously, how should the paper printing be scheduled on the machines in order to finish the order as early as possible? FURTHER INFO: `Applications of optimization with Xpress-MP', Section 7.3 `Job shop scheduling' (c) 2008 Fair Isaac Corporation author: S. Heipcke, 2002, rev. Nov. 2017 *******************************************************!) model "Job shop" uses "mmxprs","mmsvg" declarations JOBS: range ! Set of jobs (wall paper types) MACH: range ! Set of machines (colors) DUR: array(MACH,JOBS) of integer ! Durations per machine and paper NUMT: array(JOBS) of integer ! Number of tasks per job SEQ: array(JOBS,MACH) of integer ! Machine sequence per job NUMD: array(MACH) of integer ! No. of jobs (disjunctions) per machine DISJ: array(MACH,JOBS) of integer ! List of jobs per machine start: dynamic array(MACH,JOBS) of mpvar ! Start times of tasks finish: mpvar ! Schedule completion time y: dynamic array(range) of mpvar ! Disjunction variables end-declarations initializations from 'jobshop.dat' DUR NUMT SEQ NUMD DISJ end-initializations forall(m in MACH, j in JOBS | DUR(m,j)>0 ) create(start(m,j)) BIGM:=sum(m in MACH, j in JOBS) DUR(m,j) ! Some (sufficiently) large value ! Precedence constraints forall(j in JOBS) PrecLast(j):= finish >= start(SEQ(j,NUMT(j)),j) + DUR(SEQ(j,NUMT(j)),j) forall(j in JOBS, m in 1..NUMT(j)-1) Prec(j,m):= start(SEQ(j,m),j)+DUR(SEQ(j,m),j) <= start(SEQ(j,m+1),j) ! Disjunctions d:=1 forall(m in MACH, i,j in 1..NUMD(m) | i<j) do create(y(d)) y(d) is_binary Disj1(m,i,j):= start(m,DISJ(m,i))+DUR(m,DISJ(m,i)) <= start(m,DISJ(m,j))+BIGM*y(d) Disj2(m,i,j):= start(m,DISJ(m,j))+DUR(m,DISJ(m,j)) <= start(m,DISJ(m,i))+BIGM*(1-y(d)) d+=1 end-do ! Bound on latest completion time finish <= BIGM ! Solve the problem: minimize latest completion time minimize(finish) ! Solution printing declarations COLOR: array(MACH) of string ! Colors printed by the machines end-declarations initializations from 'jobshop.dat' COLOR end-initializations writeln("Total completion time: ", getobjval) write(" ") forall(j in JOBS) write(strfmt(j,6)) writeln forall(m in MACH) do write(strfmt(COLOR(m),-7)) forall(j in JOBS) if(DUR(m,j)>0) then write(strfmt(getsol(start(m,j)),3), "-", getsol(start(m,j))+DUR(m,j)) else write(strfmt(" ",6)) end-if writeln end-do ! Solution drawing declarations JobGraph: array(JOBS) of string end-declarations svgsetgraphviewbox(0,0,round(getobjval),12*(max(m in MACH)m)+1) svgsetgraphscale(5) svgsetgraphlabels("Time","") forall(j in JOBS) do JobGraph(j):= "J"+j svgaddgroup(JobGraph(j), "Job "+j ) svgsetstyle(SVG_FILL,SVG_CURRENT) end-do forall(m in MACH, j in JOBS) svgaddrectangle(JobGraph(j), getsol(start(m,j)), 10*m, DUR(m,j), 4) svgaddgroup("M", "", SVG_BLACK) forall(m in MACH) svgaddtext(0,10*m-2,COLOR(m)) svgsave("jobshop.svg") svgrefresh svgwaitclose("Close browser window to terminate model execution.", 1) end-model | |||||||||

Copyright 2017 Fair Isaac Corporation. |