TomSym Sequencing Jobs on a Bottleneck Machine: Difference between revisions
(Created page with "{{Part Of Manual|title=the TomSym Manual|link=TomSym Manual}} ==Problem description== In workshops it frequently happens that a single machine determines the through...") |
No edit summary |
||
Line 9: | Line 9: | ||
Task time windows and durations | Task time windows and durations | ||
<pre> | |||
+------------+--+--+--+--+--+--+--+ | +------------+--+--+--+--+--+--+--+ | ||
|Job | 1| 2| 3| 4| 5| 6| 7| | |Job | 1| 2| 3| 4| 5| 6| 7| | ||
Line 16: | Line 17: | ||
|Due date |10|21|15|10| 5|15|22| | |Due date |10|21|15|10| 5|15|22| | ||
+------------+--+--+--+--+--+--+--+ | +------------+--+--+--+--+--+--+--+ | ||
</pre> | |||
==Variables== | ==Variables== | ||
<pre> | |||
releasedate Release dates of jobs (row 1 in table) | releasedate Release dates of jobs (row 1 in table) | ||
duration Time to perform a job (row 2 in table) | duration Time to perform a job (row 2 in table) | ||
duedate Deadline of each job (row 3 in table) | duedate Deadline of each job (row 3 in table) | ||
</pre> | |||
==Reference== | ==Reference== |
Revision as of 17:25, 2 November 2011
This page is part of the TomSym Manual. See TomSym Manual. |
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;
rnk = tom('rnk',j,k,'int');
start = tom('start',k,1,'int');
% All slots are integers
bnds = {0 <= rnk <= 1, start >= 0};
% Assignment constraint one job per rank.
con1 = {sum(rnk,2) == 1};
% Assignment constraint one rank per job.
con2 = {sum(rnk,1) == 1};
% Release constraints.
con3 = {start >= (releasedate'*rnk)'};
% No simultaneous constraints
con4 = {start(2:end) >= start(1:end-1) + (duration'*rnk(:,1:end-1))'};
% Objective 1
objective = start(end) + sum(duration'*rnk(:,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'*rnk)'};
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'*rnk)'};
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.rnk, sol2.start, sol2.comp]; % results from 1 and 2
sequence3 = [sol3.rnk, 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 Time for symbolic processing: 0.035047 seconds Starting numeric solver ===== * * * =================================================================== * * * TOMLAB - TOMLAB Development license 999007. Valid to 2011-12-31 ===================================================================================== 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 24 CPU time: 0.015600 sec. Elapsed time: 0.005000 sec. Problem type appears to be: mip Time for symbolic processing: 0.043863 seconds Starting numeric solver ===== * * * =================================================================== * * * TOMLAB - TOMLAB Development license 999007. Valid to 2011-12-31 ===================================================================================== 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 34 CPU time: 0.343202 sec. Elapsed time: 0.163000 sec. Problem type appears to be: mip Time for symbolic processing: 0.052287 seconds Starting numeric solver ===== * * * =================================================================== * * * TOMLAB - TOMLAB Development license 999007. Valid to 2011-12-31 ===================================================================================== Problem: --- 1: Sequencing with Bottleneck f_k 18.000000000000000000 f(x_0) 0.000000000000000000 Solver: CPLEX. EXIT=0. INFORM=101. CPLEX Branch-and-Cut MIP solver Optimal integer solution found FuncEv 75 Elapsed time: 0.007000 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