% on the current point and the current temperature % NEWX = MULPROCPERMUTE(optimValues,problemData) generate a point based % MULPROCPERMUTE Moves one random task to a different processor. Here we display our custom annealing function.įunction schedule = mulprocpermute(optimValues,problemData) 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). The custom annealing function for the multiprocessor scheduling problem will take a job schedule as input. A trial point for the multiprocessor scheduling problem is a matrix of processor (rows) and tasks (columns) as discussed before. This section shows how to create and use the required custom annealing function. 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. For example, if we want simulannealbnd to use "sampleSchedule" as decision variable, a custom data type can be specified using a matrix of integers. You can use any valid MATLAB® data structure you like as decision variable. However, if the DataType option is set to 'custom' the simulated annealing solver can also work on optimization problems involving arbitrary data types. Therefore, the annealing function for generating subsequent points assumes that the current point is a vector of type double. SampleSchedule(processorID,index(1)) = task Įnd Simulated Annealing For a Custom Data Typeīy default, the simulated annealing algorithm solves optimization problems assuming that the decision variables are double data types. Index = find(sampleSchedule(processorID,:)=0) ProcessorID = 1 + floor(rand*(numberOfProcessors)) SampleSchedule = zeros(numberOfProcessors,numberOfTasks) % Random distribution of task on processors (starting point) We also define a "sampleSchedule" which will be our starting point input to simulannealbnd. The different coefficients for the various rows represent the fact that different processors work with different speeds. Here we define our number of tasks, number of processors, and lengths array. For example, the schedule 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. 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. We can represent a schedule in a similar manner. The amount of time "t" that the processor "i" takes to complete the task "j" will be stored in lengths(i,j). Now we can store the amount of time a given job will take on a given processor in a matrix called "lengths". Similarly, each processor is represented by an integer between 1 and the number of processors. We come up with the following scheme: first, let each task be represented by an integer between 1 and the total number of tasks. The goal of the problem is to determine the shortest schedule for the given set of tasks.įirst we determine how to express this problem in terms of a custom data type optimization problem that simulannealbnd function can solve. We call an assignment of all jobs to available processors a "schedule". ![]() ![]() Each processor runs independently, but each can only run one job at a time. Time taken to complete a task by a processor is also provided as data. The number of processors and number of tasks are given. For this example, we select saplotbestf, which plots the best function value every iteration, saplottemperature, which shows the current temperature in each dimension at every iteration, saplotf, which shows the current function value (remember that the current value is not necessarily the best one), and saplotstopping, which plots the percentage of stopping criteria satisfied every ten iterations.The multiprocessor scheduling problem consists of finding an optimal distribution of tasks on a set of processors. To select multiple plot functions, set the PlotFcn option via the optimoptions function. The toolbox contains a set of plot functions to choose from, or you can provide your own custom plot functions. Plot functions are selected using optimoptions. This feature is useful for visualizing the performance of the solver at run time. Simulannealbnd can accept one or more plot functions through an 'options' argument. Note that when you run this example, your results may be different from the results shown above because simulated annealing algorithm uses random numbers to generate points. The best function value found was : 2.98211
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |