Indian Journal of Science and Technology

Abstract

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.
Keywords: Algorithm, Branch Tree, Branch & Bound, Directed Graph, Gantt Chart, Makespan, Percentage Improvements, Three Machines Scheduling, Transportation Time, Weighted Mean Flowtime