Minimizing makespan subject to minimum total absolute deviation of completion time on identical parallel machines

摘要

This study addresses the identical parallel machine scheduling problem with the objective of minimizing makespan subject to minimum total absolute deviation of job completion time (TADC). An optimization algorithm is first proposed to solve TADC on an identical parallel machine and an iterative procedure based on a polynomial binary integer programming model is then proposed to minimize makespan. Computational experiments show that the proposed algorithm is efficient. The worst case performance, which refers to the largest average execution for each scenario of the experiments, is 229.10 seconds for the problem with n = 200, m = 30 and pj from a uniform [1,100].