An improved mixed-integer programming approach for bi-objective parallel machine scheduling and location. (December 2022)

• Record Type: Journal Article
• Authors: Wu, Peng; Wang, Yun; Cheng, Junheng; Li, Yantong
• Is Part Of: Computers & industrial engineering. Volume 174(2022)
• Publication Date: 2022-12
• Subjects: Parallel machine scheduling and location -- Bi-objective optimization -- Mixed-integer programming -- Valid inequalities; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2022.108813
• Languages: English
• ISSNs: 0360-8352

Abstract

Abstract: 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 NP-hard 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 ɛ -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%. Highlights: A bi-objective parallel machine scheduling and location problem is studied. A novel efficient bi-objective mixed-integer linear programming model is developed. Valid inequalities are proposed to strengthen the proposed model. An ɛ -constraint based on fuzzy-logic method is proposed to suggest Pareto-optimal solutions.