www.gusucode.com > globaloptim 案例源码程序 matlab代码 > globaloptim/samultiprocessordemo.m

    %% Multiprocessor Scheduling using Simulated Annealing with a Custom Data Type
% This example shows how to use simulated annealing to minimize a
% function using a custom data type. Here simulated annealing is customized
% to solve the multiprocessor scheduling problem.

%% Multiprocessor Scheduling Problem
% The multiprocessor scheduling problem consists of finding an optimal
% distribution of tasks on a set of processors. The number of processors and
% number of tasks are given. Time taken to complete a task by a processor is
% also provided as data. Each processor runs independently, but each can only
% run one job at a time.  We call an assignment of all jobs to available
% processors a "schedule".  The goal of the problem is to determine the shortest
% schedule for the given set of tasks.

%%
% First we determine how to express this problem in terms of a custom data type
% optimization problem that |simulannealbnd| function can solve. We come up with
% the following scheme: first, let each task be represented by an integer
% between 1 and the total number of tasks. Similarly, each processor is
% represented by an integer between 1 and the number of processors. Now we can
% store the amount of time a given job will take on a given processor in a
% matrix called "lengths". The amount of time "t" that the processor "i" takes
% to complete the task "j" will be stored in lengths(i,j).  
%
% We can represent a schedule in a similar manner. In a given schedule, the rows
% (integer between 1 to number of processors) will represent the processors and
% the columns (integer between 1 to number of tasks) will represent the tasks.
% For example, the schedule [1 2 3;4 5 0;6 0 0] would be tasks 1, 2, and 3
% performed on processor 1, tasks 4 and 5 performed on processor 2, and task 6
% performed on processor 3.
%%
% Here we define our number of tasks, number of processors, and lengths array.
% The different coefficients for the various rows represent the fact that
% different processors work with different speeds.  We also define a
% "sampleSchedule" which will be our starting point input to |simulannealbnd|.

rng default % for reproducability
numberOfProcessors = 11;
numberOfTasks = 40;
lengths = [10*rand(1,numberOfTasks);
           7*rand(1,numberOfTasks);
           2*rand(1,numberOfTasks);
           5*rand(1,numberOfTasks);
           3*rand(1,numberOfTasks);
           4*rand(1,numberOfTasks);
           1*rand(1,numberOfTasks);
           6*rand(1,numberOfTasks);
           4*rand(1,numberOfTasks);
           3*rand(1,numberOfTasks);
           1*rand(1,numberOfTasks)];
       
% Random distribution of task on processors (starting point)
sampleSchedule = zeros(numberOfProcessors,numberOfTasks);
for task = 1:numberOfTasks
    processorID = 1 + floor(rand*(numberOfProcessors));
    index = find(sampleSchedule(processorID,:)==0);
    sampleSchedule(processorID,index(1)) = task;
end

%% Simulated Annealing For a Custom Data Type
% By default, the simulated annealing algorithm solves optimization
% problems assuming that the decision variables are double data types.
% Therefore, the annealing function for generating subsequent points assumes
% that the current point is a vector of type double. However, if the |DataType|
% option is set to 'custom' the simulated annealing solver can also work on
% optimization problems involving arbitrary data types. You can use any valid
% MATLAB(R) data structure you like as decision variable. For example, if we want
% |simulannealbnd| to use "sampleSchedule" as decision variable, a custom data
% type can be specified using a matrix of integers. In addition to setting the
% |DataType| option to 'custom' we also need to provide a custom annealing
% function via the |AnnealingFcn| option that can generate new points.

%% Custom Annealing Functions
% This section shows how to create and use the required custom annealing
% function. A trial point for the multiprocessor scheduling problem is a 
% matrix of processor (rows) and tasks (columns) as discussed before.  The
% custom annealing function for the multiprocessor scheduling problem will take
% a job schedule as input. The annealing function will then modify this schedule
% and return a new schedule that has been changed by an amount proportional to
% the temperature (as is customary with simulated annealing). Here we display
% our custom annealing function.
type mulprocpermute.m

%% Objective Function
% We need an objective function for the multiprocessor scheduling problem. The
% objective function returns the total time required for a given schedule (which
% is the maximum of the times that each processor is spending on its tasks).  As
% such, the objective function also needs the lengths matrix to be able to
% calculate the total times.  We are going to attempt to minimize this total
% time. Here we display our objective function
type mulprocfitness.m

%%
% |simulannealbnd| will call our objective function with just one argument |x|,
% but our fitness function has two arguments: |x| and "lengths". We can use
% an anonymous function to capture the values of the additional argument,
% the lengths matrix. We create a function handle 'ObjectiveFcn' to an
% anonymous function that takes one input |x|, but calls 'mulprocfitness'
% with |x| and "lengths". The variable "lengths" has a value when the
% function handle 'FitnessFcn' is created so these values are captured by
% the anonymous function.

% lengths was defined earlier
fitnessfcn = @(x) mulprocfitness(x,lengths);

%%
% We can add a custom plot function to plot the length of time that the
% tasks are taking on each processor.  Each bar represents a processor, and
% the different colored chunks of each bar are the different tasks.
type mulprocplot.m

%%
% But remember, in simulated annealing the current schedule is not
% necessarily the best schedule found so far. We create a second custom
% plot function that will display to us the best schedule that has been
% discovered so far.
type mulprocplotbest.m

%% Simulated Annealing Options Setup
% We choose the custom annealing and plot functions that we have created,
% as well as change some of the default options. |ReannealInterval| is set to
% 800 because lower values for |ReannealInterval| seem to raise the temperature
% when the solver was beginning to make a lot of local progress. We also
% decrease the |StallIterLimit| to 800 because the default value makes the
% solver too slow. Finally, we must set the |DataType| to 'custom'.
options = optimoptions(@simulannealbnd,'DataType', 'custom', ...
    'AnnealingFcn', @mulprocpermute, 'MaxStallIterations',800, 'ReannealInterval', 800, ...
    'PlotFcn', {{@mulprocplot, lengths},{@mulprocplotbest, lengths},@saplotf,@saplotbestf});
%%
% Finally, we call simulated annealing with our problem information.
schedule = simulannealbnd(fitnessfcn,sampleSchedule,[],[],options);
% Remove zero columns (all processes are idle)
maxlen = 0;
for i = 1:size(schedule,1)
    if max(nnz(schedule(i,:)))>maxlen
        maxlen = max(nnz(schedule(i,:)));
    end
end
% Display the schedule
schedule = schedule(:,1:maxlen)