Title: A multi-machine bicriteria flow shop scheduling with sequence dependent setup time

Authors: Meenakshi Sharma; Sameer Sharma; Nidhi Joshi

Addresses: Department of Applied Sciences, KC College of Engineering and IT, Nawanshahr, India ' SPN College, Swami Premanand Mahavidyalaya, Mukerian, Punjab, India ' Department of Mathematics, Arya College, Ludhiana, India

Abstract: Bicriteria flow shop scheduling problem with sequence dependent setup time (BPFSSP/SDST) is addressed in this paper. The objective of scheduling problem is to minimise weighted sum of makespan and system utilisation time, when both criteria are equal weighted. To solve the referred scheduling problem in small size machine-job environment, a mixed-integer programming model is developed and implemented. Since permutation flow shop scheduling problem with SDST is NP-complete in nature, therefore, the heuristic approach based on Nawaz, Enscore, Ham (NEH) neighbourhood structure and metaheuristic approach of hybrid iterated greedy algorithm with delay time, are proposed and implemented to optimise aforementioned scheduling bicriteria. The computation experiment is carried out to evaluate the performance of all developed heuristics and metaheuristics on varying size job-machine environment. The comparative analysis reported with response variable average relative percentage deviation (ARPD) verifies the effectiveness of proposed computation techniques over existing one's in solving the referred scheduling problem.

Keywords: scheduling; bicriteria; sequence dependent setup time; iterated greedy algorithms; local search.

DOI: 10.1504/IJMOR.2025.147021

International Journal of Mathematics in Operational Research, 2025 Vol.31 No.2, pp.182 - 215

Received: 25 Aug 2023
Accepted: 29 Aug 2023
Published online: 10 Jul 2025 *

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