Min Min Max Min PDF

Preview

Summary

min min max min explanation...

Description

In the batch-mode heuristics, tasks are collected into a set known as meta-task (MT). These sets are mapped at prescheduled times called mapping events. Some occurrences of this kind are: 1. Min-Min: Min-Min Minimum completion time for each task in min-min is computed for all machines. The task with overall minimum completion time is chosen and assigned to corresponding machine. The newly mapped task is removed and the process is repeated till all tasks are mapped. Min-min is a simple and fast algorithm capable of good performance. Even GA “seeds” a population with a min-min chromosome to ensure good performance. Min-min schedules “best case” tasks first generating good schedules. Assigning small task first is it drawback. Thus, smaller tasks are executed first and then few larger tasks are executed while many machines are idling, resulting in poor machine use. Min-Min begins with the set MT of all unassigned tasks. As shown below, firstly it computes minimum completion time CTij for all tasks in MT on all resources (lines 1-3). Then two main stages of this algorithm begins. In the first phase, the set of minimum expected completion time for each task in MT is found (lines 5-6). In the second phase, the task with the overall minimum expected completion time from MT is chosen and assigned to the corresponding resource (lines 7-8). Then this task is removed from MT and the process is repeated until all tasks in the MT are mapped (lines 9-11). It is also one of the scheduling algorithms implemented. This heuristic takes O(s2m)time.

To minimize the overall make span of the tasks on machines and provide the better performance min-min and max-min algorithms are designed. These algorithms are simulated under spaceshared and time-shared mode to get minimum make span. Min-Min algorithm has following procedure: Phase 1: First computes the completion time of every task on each machine and then for every task select the machine which processes the tasks in minimum possible time. Phase2: Among all the tasks in Meta task the task with minimum completion time is selected and is assigned to machine on which minimum execution time is expected. Max-Min algorithm follows the following procedure: Phase1: First computes the completion time of every task on each machine and then for every task chooses the machine which processes the tasks in minimum possible time Phase2: Among all the tasks in Meta Task the task with maximum completion time is selected and is assigned to machine. The task is removed from the list of Meta Task and the procedure continues until Meta Task list is empty. Min–Min algorithm: This chooses small tasks for execution first, which in turn delays bigger tasks for long. • Max – Min algorithm: This chooses large tasks for execution first leading to delays in smaller tasks. In this reading, the performance of the min-min and max-min scheduling algorithm are investigated. Both the algorithms are widely used.

2. Max-Min: Max-Min is very similar to Min-Min, except in phase 2. Max-Min assigns task with maximum expected completion time to the corresponding resource, in phase 2; that is, replacing the underlined word in algorithm above minimum with maximum. So, it takes O(s2m) time, too. It is also one of the heuristics implemented in SmartNet. MaxMin heuristic is similar to min-min algorithm. The minimum completion times set is

calculated for each task and that with overall maximum completion time is selected and assigned to a corresponding machine. This algorithm does better than min-min algorithm where when short tasks outnumber long ones. For e.g. if there is one long task, max-min algorithm executes short tasks concurrently with long task. Max-min is similar to minmin. Again each job’s minimum completion time is established, but a job with maximum minimum completion time is assigned a corresponding processor.

The figure above is an example tree for Max-Min algorithm. The figure shows the flowchart for Max-Min algorithm. The algorithm calculates each resource’s submitted tasks expected completion time. Then task with overall maximum expected execution time (Largest Task) is assigned a resource with minimum overall completion time (Slowest Resource). The Max-Min algorithm: for all submitted tasks Ti in meta-task M v for all resource Rj Cij = Eij+ rj

find task Tk cost maximum execution time (largest task) assign task Tk to the resource Rj which gives the minimum completion time (Slowest resource) remove task Tk from Meta-task set update rj for selected Rj. update Cij for all j While meta-task not empty Find task Tk cost maximum completion time Assign task Tk to resource Rj which gives minimum execution time (Faster Resource) Remove Task Tk from meta-task set Update rj for selected Rj Update Cij for all...