Sequencing Jobs on a Bottleneck Machine
Contents
Problem description
In workshops it frequently happens that a single machine determines the throughput of the entire production (for example, a machine of which only one is available, the slowest machine in a production line, etc.). This machine is called the critical machine or the bottleneck. In such a case it is important to schedule the tasks that need to be performed by this machine in the best possible way. The aim of the problem is to provide a simple model for scheduling operations on a single machine and that may be used with different objective functions. We shall see here how to minimize the total processing time, the average processing time, and the total tardiness. A set of tasks (or jobs) is to be processed on a single machine. The execution of tasks is non-preemptive (that is, an operation may not be interrupted before its completion). For every task i its release date and duration are given. For the last optimization criterion (total tardiness), a due date (latest completion time) is also required to measure the tardiness, that is, the amount of time by which the completion of jobs exceeds their respective due dates. The following table lists the data for our problem.
What is the optimal value for each of the objectives: 1 - minimizing the total duration of the schedule (= makespan)? 2 - minimizing the mean processing time? 3 - minimizing the total tardiness?
Task time windows and durations
+------------+--+--+--+--+--+--+--+ |Job | 1| 2| 3| 4| 5| 6| 7| +------------+--+--+--+--+--+--+--+ |Release date| 2| 5| 4| 0| 0| 8| 9| |Duration | 5| 6| 8| 4| 2| 4| 2| |Due date |10|21|15|10| 5|15|22| +------------+--+--+--+--+--+--+--+
Variables
releasedate Release dates of jobs (row 1 in table) duration Time to perform a job (row 2 in table) duedate Deadline of each job (row 3 in table)
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
releasedate = [2 5 4 0 0 8 9]'; duration = [5 6 8 4 2 4 2]'; duedate = [10 21 15 10 5 15 22]'; j = 7; k = 7; rank = tom('rank',j,k,'int'); start = tom('start',k,1,'int'); % All slots are integers bnds = {0 <= rank <= 1, start >= 0}; % Assignment constraint one job per rank. con1 = {sum(rank,2) == 1}; % Assignment constraint one rank per job. con2 = {sum(rank,1) == 1}; % Release constraints. con3 = {start >= (releasedate'*rank)'}; % No simultaneous constraints con4 = {start(2:end) >= start(1:end-1) + (duration'*rank(:,1:end-1))'}; % Objective 1 objective = start(end) + sum(duration'*rank(:,end)); constraints = {bnds, con1, con2, con3, con4}; options = struct; options.solver = 'cplex'; options.name = 'Sequencing with Bottleneck'; sol1 = ezsolve(objective,constraints,[],options); % Objective 2 comp = tom('comp',k,1,'int'); bnds2 = {comp >= 0}; con5 = {comp == start + (duration'*rank)'}; objective = sum(comp); constraints = {constraints, bnds2, con5}; sol2 = ezsolve(objective,constraints,[],options); % Objective 3 late = tom('late',k,1,'int'); bnds3 = {late >= 0}; con6 = {late >= comp - (duedate'*rank)'}; constraints = {constraints, bnds3, con6}; objective = sum(late); sol3 = ezsolve(objective,constraints,[],options); PriLev = 1; if PriLev > 0 j = length(releasedate); % number of jobs sequence2 = [sol2.rank, sol2.start, sol2.comp]; % results from 1 and 2 sequence3 = [sol3.rank, sol3.start, sol3.comp, sol3.late]; % results from 3 sequence2(find(sequence2(1:7*7)<0.1)) = 0; % remove bad zeros sequence3(find(sequence3(1:7*7)<0.1)) = 0; % remove bad zeros s2 = []; % blank sequence s3 = []; % blank sequence for t = 1:j, s2 = [s2 find(sequence2(t,1:j))]; s3 = [s3 find(sequence3(t,1:j))]; end disp(['An order to minimize duration (=' ... num2str(sequence2(j,j+2)) ') and to minimize mean '... 'processing time (=' num2str(sequence2(j,j+2)/j) ')']) disp(num2str(s2)) disp(' ') tard = sum(sequence3(:,size(sequence3,2))); disp(['An order to minimize tardiness (=' num2str(tard) ')' ]) disp(num2str(s3)) disp(' ') 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: Sequencing with Bottleneck f_k 31.000000000000000000
f(x_0) 0.000000000000000000
Solver: CPLEX. EXIT=0. INFORM=101.
CPLEX Branch-and-Cut MIP solver
Optimal integer solution found
FuncEv 42
Problem type appears to be: mip
===== * * * =================================================================== * * *
TOMLAB - Tomlab Optimization Inc. Development license 999001. Valid to 2010-02-05
=====================================================================================
Problem: --- 1: Sequencing with Bottleneck f_k 103.000000000000000000
f(x_0) 0.000000000000000000
Solver: CPLEX. EXIT=0. INFORM=101.
CPLEX Branch-and-Cut MIP solver
Optimal integer solution found
FuncEv 51
CPU time: 0.015625 sec. Elapsed time: 0.016000 sec.
Problem type appears to be: mip
===== * * * =================================================================== * * *
TOMLAB - Tomlab Optimization Inc. Development license 999001. Valid to 2010-02-05
=====================================================================================
Problem: --- 1: Sequencing with Bottleneck f_k 18.000000000000000000
sum(|constr|) 0.000000000000007994
f(x_k) + sum(|constr|) 18.000000000000007000
f(x_0) 0.000000000000000000
Solver: CPLEX. EXIT=0. INFORM=101.
CPLEX Branch-and-Cut MIP solver
Optimal integer solution found
FuncEv 70
CPU time: 0.015625 sec. Elapsed time: 0.016000 sec.
An order to minimize duration (=31) and to minimize mean processing time (=4.4286)
3 6 7 2 1 5 4
An order to minimize tardiness (=18)
2 5 7 3 1 4 6