Particle Swarm Optimization Algorithm for Unrelated Parallel Machine Scheduling with Release Dates

We consider the NP-hard problem of minimizing makespan for <svg style="vertical-align:-0.1638pt;width:8.6625004px;" id="M1" height="7.9499998" version="1.1" viewBox="0 0 8.6625004 7.9499998" width="8.6625004" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns="http://www.w3.org/2000/svg"> <g transform="matrix(.017,-0,0,-.017,.062,7.675)"><path id="x1D45B" d="M495 86q-46 -47 -87 -72.5t-63 -25.5q-43 0 -16 107l49 210q7 34 8 50.5t-3 21t-13 4.5q-35 0 -109.5 -72.5t-115.5 -140.5q-21 -75 -38 -159q-50 -10 -76 -21l-6 8l84 340q8 35 -4 35q-17 0 -67 -46l-15 26q44 44 85.5 70.5t64.5 26.5q35 0 10 -103l-24 -98h2 q42 56 97 103.5t96 71.5q46 26 74 26q9 0 16 -2.5t14 -11.5t9.5 -24.5t-1 -44t-13.5 -68.5q-30 -117 -47 -200q-4 -19 -3.5 -25t6.5 -6q21 0 70 48z" /></g> </svg> jobs on <svg style="vertical-align:-0.1638pt;width:13.5375px;" id="M2" height="7.9499998" version="1.1" viewBox="0 0 13.5375 7.9499998" width="13.5375" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns="http://www.w3.org/2000/svg"> <g transform="matrix(.017,-0,0,-.017,.062,7.675)"><path id="x1D45A" d="M766 88q-40 -45 -83.5 -72.5t-63.5 -27.5q-39 0 -16 103l49 224q15 68 -10 68q-36 0 -112.5 -78.5t-105.5 -133.5q-27 -101 -38 -165q-35 -4 -77 -18l-6 6q42 153 70 288q12 55 10 78t-19 23q-38 0 -114 -80.5t-101 -131.5q-24 -68 -41 -165q-36 -3 -76 -18l-8 6 q56 202 87 347q7 33 -3 33q-8 0 -31.5 -17.5t-41.5 -35.5l-12 28q42 45 84 72t63 27q44 0 10 -124l-20 -75h2q92 121 193 178q36 21 64 21q62 0 28 -159l-8 -37h2q50 67 103.5 112t94.5 65q39 19 62 19q60 0 23 -156l-45 -189q-9 -39 2 -39q17 0 71 49z" /></g> </svg> unrelated parallel machines with release dates in this research. A heuristic and a very effective particle swarm optimization (PSO) algorithm have been proposed to tackle the problem. Two lower bounds have been proposed to serve as a basis for comparison for large problem instances. Computational results show that the proposed PSO is very accurate and that it outperforms the existing metaheuristic.