Flow-Shop Scheduling
Contents
Problem description
A workshop that produces metal pipes on demand for the automobile industry has three machines for bending the pipes, soldering the fastenings, and assembling the links. The workshop has to produce six pieces, for which the durations of the processing steps (in minutes) are given in the following table. Every workpiece first goes to bending, then to soldering, and finally to assembly of the links. Once started, any operations must be carried out without interruption, but the workpieces may wait between the machines.
Processing durations in minutes
+---------+-+-+-+-+-+-+ |Workpiece|1|2|3|4|5|6| +---------+-+-+-+-+-+-+ |Bending |3|6|3|5|5|7| |Soldering|5|4|2|4|4|5| |Assembly |5|2|4|6|3|6| +---------+-+-+-+-+-+-+
Every machine only processes one piece at a time. A workpiece may not overtake any other by passing onto the following machine. This means that if at the beginning a sequence of the workpieces is established, they will be processed on every machine in exactly this order. Which is the sequence of workpieces that minimizes the total time for completing all pieces?
Variables
nummachines The number of machines proctimes Time to process a workpiece in a machine
Reference
Applications of optimization... Gueret, Prins, Seveaux
% Marcus Edvall, Tomlab Optimization Inc, E-mail: tomlab@tomopt.com % Copyright (c) 2005-2009 by Tomlab Optimization Inc., $Release: 7.2.0$ % Written Oct 7, 2005. Last modified Apr 8, 2009.
Problem setup
nummachines = 3; proctimes = [3 6 3 5 5 7;... 5 4 2 4 4 5;... 5 2 4 6 3 6]; n1 = size(proctimes,2); % Number of jobs (j in JOBS) n2 = size(proctimes,2); % Number of ranks (k in RANKS) n3 = nummachines; % Number of machines (m in MACH) rank = tom('rank',n1,n2,'int'); empty = tom('empty',n3,n2); wait = tom('wait',n3,n2); % All slots are integers. bnds1 = {0 <= rank <= 1}; % Assignment constraint one job per rank. con1 = {sum(rank,1) == 1}; % Assignment constraint one rank per job. con2 = {sum(rank,2) == 1}; % Relationship between the end of job rank k on machine m and start of job % on machines m+1 duration = tom('duration',n3,n2); durcon = {}; for m=1:n3 for k=1:n2 durcon{(m-1)*n2+k} = {duration(m,k) == sum(proctimes(m,:)*rank(:,k))}; end end con3 = {empty(1:end-1,1:end-1) + duration(1:end-1,2:end) + ... wait(1:end-1,2:end) == wait(1:end-1,1:end-1) + ... duration(2:end,1:end-1) + empty(2:end,1:end-1)}; % Empty and Wait are zeros when starting, set in bounds bnds2 = {empty(:,1:end-1) >= 0}; bnds3 = {wait(1:end-1,:) >= 0}; bnds4 = {empty(1,1:end-1) == 0}; bnds5 = {wait(1:end-1,1) == 0}; % Objective objective = sum(sum(proctimes(1:end-1,:)*rank(1:end,1))) + sum(sum(empty(end,1:end-1))); constraints = {bnds1, bnds2, bnds3, bnds4, bnds5, con1, con2, con3, durcon}; options = struct; options.solver = 'cplex'; options.name = 'Flow Shop Scheduling'; sol = ezsolve(objective,constraints,[],options); PriLev = 1; if PriLev > 0 p = size(proctimes,2); % number of pieces m = nummachines; % number of machines order = round(sol.rank); wait1 = round(sol.wait(1,:)); % wait before machine 1 wait2 = round(sol.wait(2,:)); % wait before machine 2 wait3 = round(sol.wait(3,:)); % wait before machine 3 proctimes = [3 6 3 5 5 7;... % the processing times 5 4 2 4 4 5;... 5 2 4 6 3 6]; sequence = [] ; % the sequence of pieces for i = 1:p, sequence = [sequence find(order(:,i))]; % insert piece by piece end disp(['A best sequence is: ' num2str(sequence)]) mt1 = []; % empty machine-times for machine 1 mt2 = []; % empty machine-times for machine 2 mt3 = []; % empty machine-times for machine 3 t11 = 0; % timepoint for entering machine 1 t12 = 0; % timepoint for exiting machine 1 t21 = 0; % timepoint for entering machine 2 t22 = 0; % timepoint for exiting machine 2 t31 = 0; % timepoint for entering machine 3 t32 = 0; % timepoint for exiting machine 3 first2 = 1; % the first piece in machine 2 first3 = 1; % the first piece in machine 3 for i = 1:length(sequence), id = sequence(i); % times in and out of machine 1 t11 = t12 + wait1(id); t12 = t11 + proctimes(1,id); % times in and out of machine 2 if first2 == 1, t21 = t12 + wait2(id); first2 = 0 ; else t21 = t22 + wait2(id); end t22 = t21 + proctimes(2,id); % times in and out of machine 3 if first3 == 1, t31 = t22 + wait3(id); first3 = 0 ; else t31 = t32 + wait3(id); end t32 = t31 + proctimes(3,id); % times in and out of machines mt1 = [mt1; t11 t12]; mt2 = [mt2; t21 t22]; mt3 = [mt3; t31 t32]; end mt = [mt1 mt2 mt3]; disp('FLOW FOR THE PIECES') for j = 1:p, disp(['piece ' num2str(sequence(j)) ' has this flow' ]) for k = 1:m, disp([' machine ' num2str(k) ': ' num2str(mt(j,(k-1)*2+1)) '-' num2str(mt(j,(k-1)*2+2)) ]) end end disp('FLOW FOR THE MACHINES') for k = 1:m, disp(['machine ' num2str(k) ' has this flow' ]) for l = 1:p, disp([' piece ' num2str(sequence(l)) ': ' ... num2str(mt(l,((k-1)*2+1))) '-' num2str(mt(l,((k-1)*2+2)))]) end end end % MODIFICATION LOG % % 051010 med Created. % 060111 per Added documentation. % 060124 per Interpretation of results upgraded. % 060126 per Moved disp to end % 090308 med Converted to tomSym
Problem type appears to be: mip
===== * * * =================================================================== * * *
TOMLAB - Tomlab Optimization Inc. Development license 999001. Valid to 2010-02-05
=====================================================================================
Problem: --- 1: Flow Shop Scheduling f_k 9.000000000000000000
sum(|constr|) 0.000000000000003166
f(x_k) + sum(|constr|) 9.000000000000003600
f(x_0) 0.000000000000000000
Solver: CPLEX. EXIT=0. INFORM=101.
CPLEX Branch-and-Cut MIP solver
Optimal integer solution found
FuncEv 53 Iter 1
CPU time: 0.015625 sec. Elapsed time: 0.016000 sec.
A best sequence is: 1 3 4 6 5 2
FLOW FOR THE PIECES
piece 1 has this flow
machine 1: 0-3
machine 2: 3-8
machine 3: 8-13
piece 3 has this flow
machine 1: 5-8
machine 2: 8-10
machine 3: 13-17
piece 4 has this flow
machine 1: 8-13
machine 2: 10-14
machine 3: 17-23
piece 6 has this flow
machine 1: 13-20
machine 2: 14-19
machine 3: 23-29
piece 5 has this flow
machine 1: 22-27
machine 2: 19-23
machine 3: 29-32
piece 2 has this flow
machine 1: 32-38
machine 2: 23-27
machine 3: 32-34
FLOW FOR THE MACHINES
machine 1 has this flow
piece 1: 0-3
piece 3: 5-8
piece 4: 8-13
piece 6: 13-20
piece 5: 22-27
piece 2: 32-38
machine 2 has this flow
piece 1: 3-8
piece 3: 8-10
piece 4: 10-14
piece 6: 14-19
piece 5: 19-23
piece 2: 23-27
machine 3 has this flow
piece 1: 8-13
piece 3: 13-17
piece 4: 17-23
piece 6: 23-29
piece 5: 29-32
piece 2: 32-34