| |||||||||

Flow-shop scheduling Description A workshop with three different machines produces six
types of pipes, for which the durations of the processing
steps are given. Every workpiece runs through the machines
in the same order. Once started, any operations must be
carried out without interruption, but the workpieces may
wait between the machines. Every machine only processes
one piece at a time. A workpiece may not overtake any
other by passing onto the following machine. Which is the
sequence of workpieces that minimizes the total time for
completing all pieces? Further explanation of this example:
'Applications of optimization with Xpress-MP',
Section 7.2 'Flow-shop scheduling'
Source Files Data Files flowshop_graph.mos (!****************************************************** Mosel Example Problems ====================== file flowshop.mos ````````````````` TYPE: Flow-shop scheduling problem DIFFICULTY: 4 FEATURES: MIP problem, alternative formulation using SOS1, graphical solution representation DESCRIPTION: A workshop with three different machines produces six types of pipes, for which the durations of the processing steps are given. Every workpiece runs through the machines in the same order. Once started, any operations must be carried out without interruption, but the workpieces may inwait between the machines. Every machine only processes one piece at a time. A workpiece may not overtake any other by passing onto the following machine. Which is the sequence of workpieces that minimizes the total time for completing all pieces? FURTHER INFO: `Applications of optimization with Xpress-MP', Section 7.2 `Flow-shop scheduling' (c) 2008 Fair Isaac Corporation author: S. Heipcke, 2002, rev. Sep. 2107 *******************************************************!) model "Flow shop" uses "mmxprs", "mmsvg" declarations NM = 3 ! Number of machines NJ = 6 ! Number of jobs MACH = 1..NM RANKS = 1..NJ JOBS = 1..NJ DUR: array(MACH,JOBS) of integer ! Durations of jobs on machines rank: array(JOBS,RANKS) of mpvar ! 1 if job j has rank k, 0 otherwise empty: array(MACH,1..NJ-1) of mpvar ! Space between jobs of ranks k and k+1 inwait: array(1..NM-1,RANKS) of mpvar ! Waiting time between machines m ! and m+1 for job of rank k start: array(MACH,RANKS) of mpvar ! Start of job rank k on machine m ! (optional) end-declarations initializations from 'flowshop.dat' DUR end-initializations ! Objective: total inwaiting time (= time before first job + times between ! jobs) on the last machine TotWait:= sum(m in 1..NM-1,j in JOBS) (DUR(m,j)*rank(j,1)) + sum(k in 1..NJ-1) empty(NM,k) ! Every position gets a job forall(k in RANKS) OneJobPos(k):= sum(j in JOBS) rank(j,k) = 1 ! Every job is assigned a rank forall(j in JOBS) JobRank(j):= sum(k in RANKS) rank(j,k) = 1 ! Relations between the end of job rank k on machine m and start of job on ! machine m+1 forall(m in 1..NM-1,k in 1..NJ-1) Prec(m,k):= empty(m,k) + sum(j in JOBS) DUR(m,j)*rank(j,k+1) + inwait(m,k+1) = inwait(m,k) + sum(j in JOBS) DUR(m+1,j)*rank(j,k) + empty(m+1,k) ! Calculation of start times (to facilitate the interpretation of results) forall(m in MACH, k in RANKS) Start(m,k):= start(m,k) = sum(u in 1..m-1,j in JOBS) DUR(u,j)*rank(j,1) + sum(p in 1..k-1,j in JOBS) DUR(m,j)*rank(j,p) + sum(p in 1..k-1) empty(m,p) ! First machine has no idle times forall(k in 1..NJ-1) empty(1,k) = 0 ! First job has no inwaiting times forall(m in 1..NM-1) inwait(m,1) = 0 forall(j in JOBS, k in RANKS) rank(j,k) is_binary (! Alternative formulations using SOS-1: forall(j in JOBS) RankSet(j):= sum(k in RANKS) k*rank(j,k) is_sos1 forall(k in RANKS) JobSet(k):= sum(j in JOBS) j*rank(j,k) is_sos1 !) ! Solve the problem minimize(TotWait) ! Solution printing writeln("Total inwaiting time for last machine: ", getobjval) write(strfmt("Item",-11)) forall(k in RANKS) write(strfmt(getsol(sum(j in JOBS) j*rank(j,k)),3)) writeln forall(m in MACH) do write("Machine ", m, ": ") forall(k in RANKS) write(strfmt(getsol(start(m,k)),3)) writeln end-do ! Solution drawing declarations JobGraph: array(JOBS) of string end-declarations svgsetgraphviewbox(0,0, max(m in MACH,k in RANKS) start(m,k).sol+max(m in MACH,j in JOBS)DUR(m,j), NM*5) svgsetgraphscale(10) svgsetgraphlabels("Time", "") forall(k in RANKS) do JobGraph(k):="J"+k svgaddgroup(JobGraph(k), "Job "+round(getsol(sum(j in JOBS) j*rank(j,k))) ) svgsetstyle(SVG_FILL, SVG_CURRENT) end-do forall(m in MACH, k in RANKS) svgaddrectangle(JobGraph(k), getsol(start(m,k)), m*4, DUR(m,round(getsol(sum(j in JOBS) j*rank(j,k)))), 1) svgaddgroup("M", "", SVG_BLACK) forall(m in MACH) svgaddtext(0,m*4-1, "Machine "+m) svgsave("flowshop.svg") svgrefresh svgwaitclose("Close browser window to terminate model execution.", 1) end-model | |||||||||

Copyright 2017 Fair Isaac Corporation. |