An iterated local search and tabu search for two-parallel machine scheduling problem to minimize the maximum total completion time

The parallel machine scheduling problems exist in many real-life industrial examples. In order to effectively utilize the machines and decline the total waiting time of jobs assigned to each machine, the maximum total completion time per machine on a parallel machine is thus addressed. Due to the NP-hardness of the problem under consideration, in this paper the authors explore an optimal solution by a branch-and-bound method, incorporating several dominances and a lower bound. In addition, the authors also adopted an iterated local search (ILS) and a Tabu search to find its near-optimal solution for the problem. The computational results on randomly generated instances illustrate that the proposed Tabu search algorithm performs better than the two existing algorithms, and the ILS method for the small jobs, but the ILS method performs better than the two existing algorithms and Tabu search algorithm for the bigger jobs.