Question

The input to the ThreeMachineMakespan is a set of n jobs each with a processing time . A feasible solution assigns each job to one of three machines. The sum of the processing times of the jobs assigned to a machine is the time that machine is required to run. The makespan is the maximum time any of the three machines must run​.

(pi}-1

Define a local search algorithm for ThreeMachineMakespan and run it on the instance {2, 2, 2, 4, 4, 6, 8, 10}

Answer 1

•Algorithm TaskSchedule_ThreeMachine(N):

•   Input: A set N jobs, each with a processing time

•   Output: A schedule of the N jobs on 3 machines with makespan(.maximum time any of the three machines must run)

• i ← 1 { 1st machine }

•   while N is not empty do

•      remove from N a job k with the smallest processing time

•      if ith machine is free then

•         schedule K on machine i

T[i]+=T[i]+Procesing_time[k] //To save processing time taken by ith machine

•      else

• i ← (i+1)mod3 and again check kth job on the machine i