An improved mixed-integer programming approach for bi-objective parallel machine scheduling and location

This paper investigates a new bi-objective parallel machine scheduling and location problem: selecting locations for available machines, assigning jobs to these located machines for processing, and sequencing the assigned jobs on each machine to optimize the location cost and makespan, simultaneously. For the challenging NPhard problem, we first develop a novel bi-objective mixed-integer linear programming (MILP) model with fewer integer variables compared with the state-of-the-art one. Then, several valid inequalities are proposed to tighten it further. We develop an epsilon-constraint based on the fuzzy-logic method to solve the bi-objective model. Computational results for benchmark instances show that the proposed approach obtains more Pareto-optimal solutions compared with the state-of-the-art one and is more than 15 times faster than it. Valid inequalities can reduce average computation time by more than 90%.

Automated summary

This paper investigates a new bi-objective parallel machine scheduling and location problem and proposes a more efficient solution method. Experimental results show that the proposed method obtains more Pareto-optimal solutions and is faster in computation.