Title: A bi-objective MILP model for an open-shop scheduling problem with reverse flows and sequence-dependent setup times

Authors: Saba Aghighi; Esmaeil Mehdizadeh; Seyed Taghi Akhavan Niaki; Amir Abbas Najafi

Addresses: Department of Industrial Engineering, Faculty of Industrial and Mechanical Engineering, Qazvin Branch, Islamic Azad University, Qazvin, Iran ' Department of Industrial Engineering, Faculty of Industrial and Mechanical Engineering, Qazvin Branch, Islamic Azad University, Qazvin, Iran ' Department of Industrial Engineering Sharif University of Technology, Azadi Ave., Tehran, Iran ' Faculty of Industrial Engineering, K. N. Toosi University of Technology, Tehran, Iran

Abstract: In this research, the scheduling problem of open-shop scheduling problem (OSSP) with sequence-dependent setup time (SDST) is investigated considering the reverse flow (assemble/disassemble flow on the same machines). The problem is formulated as a bi-objective mixed-integer linear programming (MILP) model. It involves reverse flows to minimise the completion time (C_max) and total tardiness. Since the OSSP is an NP-hard problem, a vibration damping-based multi-objective optimisation algorithm (MOVDO) is employed to solve large test problems in a reasonable runtime. Analysing the results of this algorithm was compared to an Epsilon-constrained method, which produced similar results in small problem sizes. Additionally, this algorithm is compared to other multi-objective algorithms, such as MOACO, MO-Cuckoo search, and NSGA-II, in terms of its performance. Based on the performance of these algorithms, we show that the proposed MOVDO algorithm performs better than the other algorithms to solve this problem. Eventually, a case study is investigated to validate the mathematical model and demonstrate the application. Comparing the proposed model to the results in the real world, the proposed model shows an improvement. [Received: 3 August 2021; Accepted: 2 April 2023]

Keywords: open-shop scheduling problem; OSSP; reverse flows; sequence-dependent setup times; SDST; vibration damping-based optimisation algorithm; MOVDO.

DOI: 10.1504/EJIE.2024.138222

European Journal of Industrial Engineering, 2024 Vol.18 No.3, pp.433 - 468

Accepted: 02 Apr 2023
Published online: 30 Apr 2024 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article