Stochastic Flowshop Scheduling Model for Two Machines

  • Neelam Tyagi Department of Mathematics, Graphic Era University, Dehradun, India
  • R. P. Tripathi Department of Mathematics, Graphic Era University, Dehradun, India
  • A. B. Chandramouli Department of Mathematics, Meerut College, Meerut, India
Keywords: Flowshop Scheduling, Transportation Times, Makespan, Utilization Times of Machine, Weighted Mean Flowtime


In this paper, we have developed a new heuristic algorithm for n jobs two machines (n*2) flowshop scheduling problem in which processing times is associated with their respective probabilities. The objective of this paper is to find the optimal sequence of jobs to minimize the makespan (total completion times of jobs) and the total mean weighted flow time of jobs. The transportation times of the first machine to second machine are also being considered. Further, jobs are attached to their weight to indicate their relative importance. We also calculated the utilization times of machines. The algorithm is justified by the numerical illustration and Gantt chart is generated to verify the effectiveness of the proposed approaches. The proposed heuristic algorithm is easy to understand and provide an important tool for decision makers.


Download data is not yet available.


Baker, K. R. (1974). Introduction to sequencing and scheduling, Wiley and Sons, New York.

Brown, A. P. G., & Lomnicki, Z. A. (1966). Some applications of the “branch-and-bound” algorithm to the machine scheduling problem. Journal of the Operational Research Society, 17(2), 173-186.

Chandramouli, A. B. (2005).Heuristic approach for n jobs, 3-machines flow shop scheduling problem involving transportation time, breakdown time and weights of jobs, Mathematical and Computational Application, 10(2), 301-305.

Chen, B., & Lee, C. Y. (2008). Logistics scheduling with batching and transportation. European Journal of Operational Research, 189(3), 871-876.

Dannenbring, D. G. (1977). An evaluation of flowshop sequencing heuristics, Management Science, 23(11), 1174-1182.

Gupta D.,& Singh, T.P.(2005). On job block open shop scheduling, the processing time associated with probability. Journal of the Indian Society of Statistics and Operations Research, 26 (1-4), 91-96.

Gupta J. N. D. (1975). Optimal schedule for specially structured flowshop. Naval Research Logistic, 22(2), 255-269.

Heydari, A. P. D. (2003). On flow shop scheduling problem with processing of jobs in a string of disjoint job blocks: fixed order jobs and arbitrary order jobs. Journal of the Indian Society of Statistics and Operations, 24, 1-4.

Ignall, E., & Schrage, L. (1965). Application of the branch and bound technique to some flow-shop scheduling problems. Operations Research, 13(3), 400-412.

Johnson, S. M. (1954). Optimal two‐and three‐stage production schedules with setup times included. Naval Research Logistics Quarterly, 1(1), 61-68.

Lomnicki, Z. A. (1965). A branch-and-bound algorithm for the exact solution of the three-machine scheduling problem. Journal of the Operational Research Society, 16(1), 89-100.

Maggu P. L., &Das,G. (1977). Equivalent jobs for job block in job sequencing, Opsearch, 14(4), 277-281.

Mitten, L. G. (1959). Sequencing n jobs on two machines with arbitrary time lags. Management Science, 5(3), 293-298.

Miyazaki, S., & Nishiyama, N. (1980). Analysis for minimizing weighted mean flow-time in flow-shop scheduling. Journal of the Operations Research Society of Japan, 23(2), 118-132.

Nawaz, M., Enscore, E. E., & Ham, I. (1983). A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega, 11(1), 91-95.

Palmer, D. S. (1965). Sequencing jobs through a multi-stage process in the minimum total time—a quick method of obtaining a near optimum. Journal of the Operational Research Society, 16(1), 101-107.

Sarin, S., & Lefoka, M. (1993). Scheduling heuristic for the n-jobm-machine flow shop. Omega, 21(2), 229-234.

Singh, T. P. (1995). On 2 xn flow-shop problems invoving job-block, transportation time, arbitrary time and break down machine time. PAMS, 21, 1-2.

Singh, T. P., Kumar, R., & Gupta, D. (2005). Optimal three stage production schedule, the processing and set up times associated with probabilities including job block criteria. InProceedings of the National Conference on FACM,463-470.

Smith R. D., & Dudek, R. A. (1967). A general algorithm for solution of n jobs, M machines sequencing problem of the flow shop. Operations Research, 15(1), 71-82.

Tyagi, N., &Chandramouli,A. B. (2014). A new heuristic algorithm for two stage flowshop scheduling problem.Proceeding of SOM 2014 IIT Roorkee,642-646.

Yoshida, T., & Hitomi, K. (1979). Optimal two-stage production scheduling with setup times separated.AIIE Transactions, 11(3), 261-263.