Parallel Machine Scheduling Problem with Machine Rental Cost and Shared Service Cost

An identical parallel machine offline scheduling problem with rental costs and shared service costs of shared machines is studied. In machine renting, manufacturers with a certain number of identical parallel machines will incur fixed rental costs, unit variable rental costs, and shared service costs when renting the shared machines. The objective is to minimize the sum of the makespan and total sharing costs. To address this problem, an integer linear programming model is established, and several properties of the optimal solution are provided. A heuristic algorithm based on the number of rented machines is designed. Finally, numerical simulation experiments are conducted to compare the proposed heuristic algorithm with a genetic algorithm and the longest processing time (LPT) rule. The results demonstrate the effectiveness of the proposed heuristic algorithm in terms of calculation accuracy and efficiency. Additionally, the experimental findings reveal that the renting and scheduling results of the machines are influenced by various factors, such as the manufacturer’s production conditions, the characteristics of the jobs to be processed, production objectives, rental costs, and shared service costs.