In this paper, an identical parallel machine problem was considered with the objective of minimizing the makespan. This problem is NP-hard in the strong sense. A mathematical formulation based on an improved arc flow model with enhanced bounds was proposed. A variable neighborhood search algorithm was proposed to obtain an upper bound. Three lower bounds from the literature were utilized in the improved arc flow model to improve the efficiency of the mathematical formulation. In addition, a graph compression technique was proposed to reduce the size of the graph. As a consequence, the improved arc flow model was compared with an arc flow model from the literature. The computational results on benchmark instances showed that the improved arc flow model outperformed the literature arc flow model at finding optimal solutions for 99.97% of the benchmark instances, with the overall percentage of the reduction in time reaching 87%.

This paper investigates a uniform parallel machine scheduling problem for makespan minimization. Due to the problem’s NP-hardness, much effort from researchers has been directed toward proposing heuristic and metaheuristic algorithms that can find an optimal or a near-optimal solution in a reasonable amount of time. This work proposes two versions of a variable neighborhood search (VNS) algorithm with five neighborhood structures, differing in their initial solution generation strategy. The first uses the longest processing time (LPT) rule, while the second introduces a novel element by utilizing a randomized longest processing time (RLPT) rule. The neighborhood structures for both versions were modified from the literature to account for the variable processing times in uniform parallel machines. We evaluated the performance of both VNS versions using a numerical example, comparing them against a genetic algorithm and a tabu search from existing literature. Results showed that the proposed VNS algorithms were competitive and obtained the optimal solution with much less effort. Additionally, we assessed the performance of the VNS algorithms on randomly generated instances. For small-sized instances, we compared their performance against the optimal solution obtained from a mathematical formulation, and against lower bounds derived from the literature for larger instances. Computational results showed that the VNS version with the randomized LPT rule (RLPT) as the initial solution (RVNS) outperformed that with the LPT rule as the initial solution (LVNS). Moreover, RVNS found the optimal solution in 90.19% of the small instances and yielded an average relative gap of about 0.15% for all cases.

This paper considers the scheduling problem of uniform parallel machines. The objective is to minimize the makespan. This problem holds practical significance and is inherently NP-hard. Therefore, solutions of the exact formulation are limited to small-sized instances. As the problem size increases, the exact formulation struggles to find optimal solutions within a reasonable time. To address this challenge, an arc flow formulation is proposed, aiming to solve larger instances. The arc flow formulation creates a pseudo-polynomial number of variables, with its size being significantly influenced by the problem’s bounds. Therefore, bounds from the literature are utilized, and symmetry-breaking rules are applied to reduce the size of the arc flow graph. To test the effectiveness of the proposed arc flow formulation, it was compared with a mathematical formulation from the literature on small instances with up to 30 jobs. Computational results showed that the arc flow formulation outperforms the mathematical formulation from the literature, solving all cases within a few seconds. Additionally, on larger benchmark instances, the arc flow formulation solved 84.27% of the cases to optimality. The maximum optimality gap does not exceed 0.072% for the instances not solved to optimality.