Total views : 285

Three Machines Flowshop Scheduling Model with Bicriterion Objective Function


  • Department of mathematics, Graphic Era University, Dehradun - 248002, Uttarakhand, India
  • Department of mathematics, Meerut College, Meerut - 250003, Uttar Pradesh, India


Objectives: To find the optimum solution for minimization of bicriterion (makespan, weighted mean flowtime) objective function of three machines flowshop scheduling problem with transportation times and weight of the jobs. Methods/Statistical Analysis: In this paper, we used two types of methodologies first one is based on a Branch and Bound (B&B) technique of exact algorithms and second one is based on Palmer approach of heuristic algorithms. First of all, we originated a new algorithm using B&B technique later on; we developed a new heuristic algorithm using Palmer approach for obtaining the optimal or near optimal sequence to minimize the bicriterion objective function of three machines scheduling problem in flowshop environments with transportation times and weights of the jobs. Comparative study between both the proposed algorithms is also considered to select the best methodology of our bicriterion objective function with the help of numerical illustration. Directed graphs, Gantt chart and Branch Tree are also generated to understand the process of lower bound and effectiveness of proposed algorithms. Findings: We solved the same numerical by constructed Branch & Bound (B&B) algorithm and Palmer based heuristic algorithm. Hence, comparatative result show that our originated B&B algorithm gives the optimal solution or better result as compare to Palmer based heuristic algorithm for minimization of bicriterion (makespan and weighted mean flowtime) objective function. We also calculated the percentage improvement of our constructive B&B algorithm over palmer based new heuristic algorithm and it is examined that constructive B&B algorithm gives the 8.33% improvement in make span and 6.52% improvement in weighted mean flowtime. The directed graph of each computational level is also originated to understand the computational process of the lower bounds easily. The Gantt chart between both the proposed algorithms is also generated to verify the effectiveness of new originated B&B algorithm. Directed graph is also generated of the optimal sequence. Finally, Branch Tree is generated to empathize the process of Lower Bound. Application/Improvements: Our constructed B&B algorithm provide an important tool for decision maker to minimize the makespan and weighted mean flowtime together as bicriterion objective function of three machine flowshop scheduling problems.


Algorithm, Branch Tree, Branch & Bound, Directed Graph, Gantt Chart, Makespan, Percentage Improvements, Three Machines Scheduling, Transportation Time, Weighted Mean Flowtime.

Full Text:

 |  (PDF views: 239)


  • Johnson SM. Optimal two and three stage production schedules with set-up times included, Nav Res Log Quart.1954; (l1):61–8.
  • Smith RD, Dudke RA. A general algorithm for solution of the n-jobs, m-machines sequencing problem of the flow shop. Operations Research. 1967; 15(1):71–82.
  • Maggu PL, Das G. On 2 x n sequencing problem with transportation time of jobs. Pure and Applied Mathematical Sciences. 1980; 32(12):1–6.
  • Ignall S. Application of the branch and bound technique to some flow shop scheduling problems. Operation Research. 1965; 13:400–12.
  • Dileepan P, Sen T. Bicriteria state scheduling research for a single machine. Omega. 1988; 16:53–9.
  • Rajendran C. Two machine flow shop scheduling problem with bicriteria. Journal of Operational Research Society. 1992; (43):871–84.
  • Gupta D, Singh TP, Kumar R. Bicriteria in a flowshop, the set up time associated with probabilities including job block concept. Proc of Contribution of Mathematics in Technology Development; 2006 May 4. p. 192–7.
  • Gupta D, Sharma S, Gulati N. Bicriteria in nx3 flow shop scheduling under specified rental policy, processing time associated with probabilities including job block criteria. Proc of International Conference on Advances in Modeling, Optimization and Computing; IIT Roorkee. 2011. p. 398– 407.
  • Prakash D. Bicriteria scheduling problems on parallel machines [PhD thesis]. Virginia: Birekshurg; 1977.
  • Lomnicki ZA. A branch and bound algorithm for the exact solution to some flow shop scheduling problems. Operational Research. 1965; 16:89–100.
  • Brown A, Lomnicki Z. Some application of branch and bound algorithm to the machine scheduling problem. Operation Research Quarterly. 1966; 17:173–86.
  • Palmer DS. Sequencing jobs through a multi stage process in the minimum total time- A quick method of obtaining a near optimum. Operations Research Quarterly. 1965; 16(1).
  • Campell HA, Duder R A, Smith ML. A heuristic algorithm for n-jobs, m-machines sequencing problem. Management Science. 1970; 16:B630–7.
  • Khodadadi A. Development of a new heuristic for three machines flow-shop scheduling problem with transportation time of jobs. World Applied Sciences Journal. 2008; 5(5):598–601.
  • Chandramouli AB. Heuristic approach for n jobs, 3 machine flow shop scheduling problem involving transportation time, breakdown time and weights of jobs. Mathematical and Computational Applications. 2005; 10:301–5.
  • Yoshida H. Optimal two stage production schedule with setup time separated. AIIE Transaction. 1979; 2:261–3.
  • Gupta D, Sharma S, Aggarwal S. Bi-objective scheduling on parallel machines with uncertain processing time. Advances in Applied Science Research. 2012; 3(2):1020–6.
  • Tyagi N, Tripathi RP, Chandramouli AB. Flexible flowshop scheduling model with four stages. Indian Journal of Science and Technology. 2016 Nov; 9(42):1–11.


  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.