A Proposed Heuristic Algorithm for n-job m-machine Job Sequencing Problems

Abstract

This paper presents an in-depth analysis of job sequencing in flow-shop scheduling problems, with a focus on exploring alternative mean-based techniques alongside the classical Johnson’s method. While Johnson’s method is widely recognized for determining optimal job sequences in two and three machine problems, this study examines the impact of applying different mean-based approaches such as the Arithmetic Mean, Harmonic Mean, Contra-harmonic Mean, and Quadratic Mean on sequencing decisions and performance outcomes. The comparative analysis is carried out using identical problem instances to ensure consistency in evaluation. Results indicate that, in certain cases, mean-based methods produce sequences identical to Johnson’s method, thereby preserving the optimal elapsed time, while in other cases, variations in job sequences occur without altering the total elapsed time, thus maintaining optimality. However, differences in machine idle times are observed, suggesting potential efficiency improvements in specific scenarios. The findings highlight that mean based methods can serve as viable alternatives to Johnson’s method, offering flexibility in sequencing decisions while retaining solution quality. This work contributes to the understanding of heuristic adaptations in classical scheduling problems and provides insights for practitioners seeking efficient scheduling strategies in manufacturing and service operations.

Dhaka Univ. J. Sci. 74(2): 341–352, 2026 (July)