A Heuristic Approach to Flow Shop Scheduling Problem in Which Processing Times Are Associated with Their Respective Probabilities with No-Idle Constraint

This paper is an attempt to study general flow shop scheduling problem in which processing time of jobs is associated with probabilities under no-idle constraint. The objective of this paper is to develop a heuristic algorithm to flowshop scheduling so that no machine remains idle during working for any given sequence of jobs. The proposed algorithm is simple, and easy to understand and provides an important tool in many practical situations for minimizing the expected hiring cost of the machines for a fixed sequence of job processing. A numerical illustration is also given to justify the proposed algorithm. 1. Introduction In flow shop scheduling problems, the objective is to obtain a sequence of jobs which when processed on the machines will optimize some well-defined criteria. Every job will go on these machines in a fixed order of machines. The research into flow shop problems has drawn a great attention in the last decades with the aim to increase the effectiveness of industrial production. Johnson [1] gave procedure for finding the optimal schedule for -jobs, two-machine flow-shop problem with minimization of the makespan (i.e., total elapsed time) as the objective. Ignall and Scharge [2] applied Branch and Bound technique for obtaining a sequence which minimizes the total flow time. In addition Adiri and Pohoryles [3] elucidated no-idle scheduling to minimize the sum of completion time. Rajendran and Chaudhuri [4] have given conditions to obtain a sequence which minimizes total flow time subject to minimum makespan in a two-stage flow shop problem. Szwarc [5], Yoshida and Hitomi [6], Anup [7], and so forth, derived the optimal algorithm for two/three or multistage flow shop problems taking into account the various constraints and criteria. Singh et al. [8] associated probabilities with processing time and setup time in their studies. Later, Gupta et al. [9] and Gupta and Singh [10] studied general flow shop problem to minimize rental cost under a predefined rental policy in which the probabilities have been associated with processing time on each machine and other scheduling problems by considering various parameters like transportation, idle/waiting operator, and so forth. Narain and Bagga [11–13] studied the flow shop problem with the objective being total rental cost. The total rental cost is minimized when idle time on all the machines is zero. Under the no-idle situation, machines work continuously without any break; that is, machines should not remain idle once they start processing the first job. The no-idle situation arises in real life