Algorithm for Minimization Case in Interval Assignment Problem

Abstract

Let A1, A2, A3 ... An, indicates the resources and 1^st , 2^nd, 3^rd, 4^th... specifies the activities. To solve the ILAPs, the succeeding steps are executed.

Step 1 : From the provided cost matrix, determine the mid-values of each interval and consider rows as workers and columns as jobs

Step 2 : Under C1 write the resource say A1, A2, A3….An. Next, determine the minimal Unit cost for every row. Whatever minimum value is existent in the respective column, pick it and write it in respect of activities under C2. Continue this process for all An rows and write the term of 1^st , 2^nd, 3^rd, 4^th...

Step 3 : If there exists a unique activity, assign this activity for the equivalent resource to attain an optimum solution. If there is no specific unique activity for the corresponding resource then the assignment could be made utilizing the subsequent steps.

Step 4 : If any resource comprises a unique activity, then assign this activity for the equivalent resource. After that, eliminate that row along with its equivalent column for which the resource has formerly been assigned.

Step 5 : Again ascertain the minimal unit cost for the resting rows. Check if it satisfies step 4 if not, verify which rows comprise only one same activity. After that, determine the difference betwixt minimum and next minimum unit cost for all such rows which comprises the same activity. Assign that activity which has a maximum difference. Eliminate such rows with its corresponding columns in which those resources were assigned