A Heuristic Approach to Optimize Rental Costs in a No-Idle Two-Stage Flow Shop Scheduling Problem

Abstract

Scheduling is an important issue for maximizing resource utilization in manufacturing. This paper deals with the no-idle two-stage flow shop scheduling problem (FSSP), from the view point of minimizing the total rental costs. The no-idle constraint, which requires continuous machine operation, is a very important constraint in real-world manufacturing systems. While classical algorithms like Johnson's Algorithm and NEH heuristic have been widely used, they usually do not take into account the optimization of the rental costs under no-idle constraints. To fill this gap, a new heuristic algorithm for finding optimum job sequence in terms of total elapsed time and total rental cost is proposed. The resulting model incorporates setup times, probabilistic processing time and job weightage to improve scheduling efficiency. A mathematical model of the problem is given, and the computational experiments were carried out for different sizes of jobs. The performance of the proposed method is compared with the well-known heuristics such as Johnson's Algorithm, Palmer's Heuristic, NEH, and Nailwal's heuristic. Experimental findings reveal that the proposed heuristic consistently outperforms conventional methods, yielding lower rental costs and improved machine utilization efficiency.