# Assembly Line Balancing

## Contents

## Problem description

An electronics factory produces an amplifier on an assembly line with four workstations. An amplifier is assembled in twelve operations between which there are certain precedence constraints. The following table indicates the duration of every task (in minutes) and the list of its immediate predecessors (the abbreviation PCB used in this table stands for printed circuit board).

The production manager would like to distribute the tasks among the four workstations, subject to the precedence constraints, in order to balance the line to obtain the shortest possible cycle time, that is, the total time required for assembling an amplifier. Every task needs to be assigned to a single workstation that has to process it without interruption. Every workstation deals with a single operation at a time. We talk about cycle time because the operations on every workstation will be repeated for every amplifier. When an amplifier is finished, the amplifiers at stations 1 to 3 advance by one station, and the assembly of a new amplifier is started at the first workstation.

List of tasks and predecessors +----+---------------------------------------+--------+------------+ |Task|Description |Duration|Predecessors| +----+---------------------------------------+--------+------------+ | 1 |Preparing the box | 3 | – | | 2 |PCB with power module | 6 | 1 | | 3 |PCB with pre-amplifier | 7 | 1 | | 4 |Filter of the amplifier | 6 | 2 | | 5 |Push-pull circuit | 4 | 2 | | 6 |Connecting the PCBs | 8 | 2,3 | | 7 |Integrated circuit of the pre-amplifier| 9 | 3 | | 8 |Adjusting the connections | 11 | 6 | | 9 |Heat sink of the push-pull | 2 | 4,5,8 | | 10 |Protective grid | 13 | 8,11 | | 11 |Electrostatic protection | 4 | 7 | | 12 |Putting on the cover | 3 | 9,10 | +----+---------------------------------------+--------+------------+

A precedence graph of the same table with times within ( ).

1 (3)

/ \ / \ / \

3 (7) 2 (6)

/ \ / | \ / \ / | \ / \ / | \

7 (9) 6 5 4 (6) (8) (4) | | | | | | | | | | | | | | 11 (4) 8 | | (11)| / \ / \ | / \ / \ | / \ / \ | /

10 (13) 9 (2)

\ / \ / \ /

12 (3)

## Variables

duration Time or each task. stations Stations available. dependsvec1 and 2 For a task t: If dependsvec1[i] = t and dependsvec2[i] = d then t depends on d.

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

duration = [3;6;7;6;4;8;9;11;2;13;4;3]; stations = 4; dependsvec1 = [2;3;4;5;6;6;7;8;9;9;9;10;10;11;12;12]; dependsvec2 = [1;1;2;2;2;3;3;6;4;5;8; 8;11; 7; 9;10]; i = length(duration); m = stations; proc = tom('proc',i,m,'int'); cycle = tom('cycle',1,1); % All slots are integers bnds = {0 <= proc <= 1, cycle >= 0}; % Every process has to go to one machine con1 = {sum(proc,2) == 1}; % Precedence constraint iter = length(dependsvec1); con2 = {}; for i=1:iter idxi = dependsvec1(i); idxj = dependsvec2(i); con2{i} = {sum(proc(idxi,:).*(1:4)) >= ... sum(proc(idxj,:).*(1:4))}; end % Cycle constraint con3 = {duration'*proc <= cycle}; % Objective objective = cycle; constraints = {bnds, con1, con2, con3}; options = struct; options.solver = 'cplex'; options.name = 'Assembly Line Balancing'; sol = ezsolve(objective,constraints,[],options); PriLev = 1; if PriLev > 0 t = length(duration); % number of tasks s = stations; % number of workstations temp = sol.proc; % reshaping distribution time = sol.cycle; % total time for i = 1:s, disp(['tasks managed by station ' ... % filter + disp num2str(i) ': ' ... num2str(find(temp(:,i))')]) end disp(['total time ' num2str(time)]) % disp the time end % MODIFICATION LOG % % 051010 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: Assembly Line Balancing f_k 20.000000000000000000 f(x_0) 0.000000000000000000 Solver: CPLEX. EXIT=0. INFORM=101. CPLEX Branch-and-Cut MIP solver Optimal integer solution found FuncEv 153 Iter 24 CPU time: 0.015625 sec. Elapsed time: 0.063000 sec. tasks managed by station 1: 1 2 3 5 tasks managed by station 2: 6 8 tasks managed by station 3: 4 7 11 tasks managed by station 4: 9 10 12 total time 20