[Python] Unbalanced Assignment problem, Partial Bound Value [closed]

Step-1: Input: m,n,ECM(,)

Step-2: Obtain the sum of each row of the ECM(,) and store the result in one-dimensional array Sum Row(,) of order m.

Step-3: Obtain the sum of each column of the ECM(,) and store the result in one-dimensional array Sum Column(,) of order n.

Step-4: Partitioned the execution cost matrix ECM(,) of order m×n to sub matrices such that the order of these matrices become square i.e. number of row should be equal to number of column. Partitioning to be made as mentioned in the following steps.

Step-4.1: Select the n job on the basis of Sum Row(,) array i.e. select the n job corresponding to most minimum sum to next minimum sum, if there is a tie select arbitrarily.

Step-4.2: Store the result in the two dimensional array ECM(,,) to form the sub matrices of the sub problem.

Step-4.3: If all the jobs are selected then go to step 4.7 else steps 4.4

Step-4.4: Repeat the step 4.1 to 4.3 until the number of jobs become less than n.

Step-4.5: Select the remaining job say r,r < n, select the r machines on the basis of Sum Column(,) array i.e. the machines corresponding to the most minimum sum to next minimum, if there is a tie select arbitrarily.

Step-4.6: Store the result in the two dimensional array ECM(,,), which is the last sub problem.

Step-4.7: List of all sub problems formed through step 4.1 to 4.6 and repeat step 5 to step 9 to solve each of these sub problems.

Step-5: for each sub problem, calculate partial bound value (PBV) of each square sub matrices Partial Upper Bound Value (PUBV)
n
∑
i=1, j=1
ai j or
n,1
∑
i=1, j=n
ai j
Partial Lower Bound Value (PLBV)
n
∑
i=1
min
n
∑
i=1, j=1
ai j!
or
n
∑
j=1
min
m
∑
i=1, j=1
ai j!

Step-6: Calculate partial bound value (PBV) of job Ji ; for i = 1
corresponding to each machine Mj
; for j = 1,2,3,···n..

Step-6.1: For ai j;i = 1; j = 1, find the minimum value of remaining columns after neglecting the corresponding row and column elements and find sum of all minimum values corresponding to that element.

Step-6.2: Repeat this process for all ai j;i = 1; j = 1,2,··· ,n.

Step-6.3: Find the Minimum value from all ai j;i = 1; j = 1,2,··· ,n and compare it with partial bound value (PBV).

Step-7: Compare the PBV.

Step-7.1: If PBV < PLBV then drop it.

Step-7.2: If PBV > PUBV then drop it.

Step-7.3: If PBV ( ≥ PLBV , ≤ PUBV ) then job Ji ; for i = 1 assigned to corresponding to that Machine Mj ; for j = 1,2,··· ,n which having minimum partial bound value.

Step-7.4: If there if tie between two PBV, then select the machine for corresponding job having their minimum execution cost.

Step-8: repeat the process for remaining m − 1 jobs till all m jobs are assigned to n machines.

Step-9: repeat the process on each sub matrices and find the minimum cost of the problem by summing execution cost of each job to corresponding machines of each of the sub matrices.

Step-10: Stop

Continue reading...