# Job Shop Scheduling

## Contents

## Problem description

A company has received an order for three types of wallpapers: one (paper 1) has a blue background with yellow patterns, another (paper 2) a green background and blue and yellow patterns, and the last (paper 3) has a yellow background with blue and green patterns. 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: for paper 1 first the blue background and then the yellow pattern is printed. After the green background for paper 2, first the blue and then the yellow patterns are printed. The printing of paper 3 starts with the yellow background, followed by the blue and then the green patterns.

p2 p1 p3 | | | V V V +-----+ +----+ --p1-> +------+ |GREEN| --p2-> |BLUE| --p2-> |YELLOW| +-----+ <-p3-- +----+ <-p3-- +------+

| | | V V V p3 p1 p2

Production flows through printing machines

The processing times differ depending on the surface that needs to be printed. The times (in minutes) for applying every color of the three paper types are given in the following table.

Times required for applying every color

+-------+------+-------+-------+-------+ |Machine|Color |Paper 1|Paper 2|Paper 3| +-------+------+-------+-------+-------+ | 1 |Blue | 45 | 20 | 12 | | 2 |Green | - | 10 | 17 | | 3 |Yellow| 10 | 34 | 28 | +-------+------+-------+-------+-------+

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?

## Variables

the colors are ordered as follows:

color1 = blue (paper 1's first color) color2 = green (paper 2's first color) color3 = yellow (paper 3's first color)

proctimes Times for the papers in the machines flow The order of colors on the paperS final The last machine for each paper bigM The total processingtimes.

## 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

proctimes = [45 20 12 10 17 10 34 28]'; flow = [1 3 0;... 2 1 3;... 3 1 2]; final = [3;3;2]; bigM = sum(sum(proctimes)); disj1 = [1 1 2 4 6 6 7]'; disj2 = [2 3 3 5 7 8 8]'; arc1 = [1 4 2 8 3]'; arc2 = [6 2 7 3 5]'; tasks = 8; start = tom('start',tasks,1); y = tom('y',length(disj1),1,'int'); finish = tom('finish',1,1); %Scalar % All slots are integers bnds1 = {start >= 0, 0 <= finish <= bigM, 0 <= y <= 1}; % Task constraint taskcon = {start(1:8) + proctimes(1:8) <= finish}; % Arc constraint arccon = {}; for i=1:length(arc1) arccon{i} = {start(arc1(i)) + proctimes(arc1(i)) <= start(arc2(i))}; end % Disj constraint disjcon = {}; for i=1:length(disj1) disjcon{i} = ... {start(disj1(i)) + proctimes(disj1(i)) <= ... start(disj2(i)) + bigM*y(i)}; disjcon{i+length(disj1)} = ... {start(disj2(i)) + proctimes(disj2(i)) <= ... start(disj1(i)) + bigM*(1-y(i))}; end constraints = {bnds1, taskcon, arccon, disjcon}; options = struct; options.solver = 'cplex'; options.name = 'Job Shop Scheduling'; sol = ezsolve(finish,constraints,[],options); PriLev = 1; if PriLev > 0 c = 3; % number of colors p = 3; % number of papers disp(['all papers are finished after ' num2str(sol.finish) ' minutes']) disp(' ') for j = 1:p, disp(['paper ' num2str(j) ':']) if j==1 colortimes = sol.start(1:3); elseif j == 2 colortimes = [0;sol.start(4:5)]; else colortimes = sol.start(6:8); end [time,col] = sort(colortimes); for i = 1:c, this_col = col(i); this_time = time(i); if this_time == 0 disp([' starts using color ' num2str(this_col) ' after ' ... num2str(this_time) ' minutes (or not at all)']) else disp([' starts using color ' num2str(this_col) ' after ' ... num2str(this_time) ' minutes']) end end end end % MODIFICATION LOG % % 060102 med Created % 060111 per Added documentation % 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: Job Shop Scheduling f_k 96.999999996000000000 sum(|constr|) 0.000000000211653345 f(x_k) + sum(|constr|) 96.999999996211656000 f(x_0) 0.000000000000000000 Solver: CPLEX. EXIT=0. INFORM=101. CPLEX Branch-and-Cut MIP solver Optimal integer solution found FuncEv 8 all papers are finished after 97 minutes paper 1: starts using color 2 after 10 minutes starts using color 3 after 30 minutes starts using color 1 after 42 minutes paper 2: starts using color 1 after 0 minutes (or not at all) starts using color 2 after 0 minutes (or not at all) starts using color 3 after 42 minutes paper 3: starts using color 3 after 0 minutes (or not at all) starts using color 2 after 30 minutes starts using color 1 after 87 minutes