An Optimized Algorithm for Flow Shop Scheduling with Rental Machines

Abstract

Efficient scheduling is critical for optimizing resource allocation and minimizing operational costs in manufacturing and service industries. Flow shop scheduling problems (FSSPs) become more complex when machines are rented instead of owned, introducing additional constraints and cost considerations. This paper proposes an optimized approach to sequencing jobs on two rented machines to achieve minimum total rental cost while maintaining productivity. The study formulates the problem mathematically, incorporates setup times and probabilities and applies a modified Johnson’s algorithm to determine the optimal job sequence. A computational analysis is performed across multiple problem sizes and compared with established heuristics, including Palmer (1985), Johnson (1954) and NEH (1983). Results demonstrate that the proposed algorithm consistently achieves lower rental costs than existing methods. This research provides a practical decision-support tool for industries facing capital constraints, helping reduce equipment rental expenses without compromising efficiency.