Mathematical models and an effective exact algorithm for unrelated parallel machine scheduling with family setup times and machine cost

This paper investigates unrelated parallel machine scheduling problems, considering machine- and sequence-dependent family setup times and machine usage costs to minimise the sum of the total weighted completion time and the total machine usage cost. The machine usage cost consists of a fixed cost and a variable cost proportional to the processing times of jobs. These features align with numerous real-world applications that include machine usage costs, for example, rental fees when customers rent machines via a cloud manufacturing platform. To address the problem, five integer programming models are developed from different perspectives. Afterwards, a modified branch-and-price algorithm (B&P) based on the set-partitioning model is proposed. To enhance the performance of B&P, we introduce two dynamic programming algorithms and a heuristic pricing algorithm, and the initial solution is generated by an improved variable neighbourhood search algorithm. Extensive experimental results show that the proposed B&P outperforms state-of-the-art mathematical models and algorithms. Notably, B&P can optimally solve instances with up to 10 machines, 100 jobs, and 12 families within half an hour. Interestingly, experimental results also show that the B&P performs significantly better when total completion time is dominated by the total variable cost of machine usage.