The problem attacked in this paper is the scheduling of n jobs on two machines which are assumed to be continuously available. All jobs are available at the beginning of the scheduling period. Setup times are included in the processing times. No preemption of jobs is allowed. The objective is the minimization of a weighted combination of the average job flowtime and the schedule makespan. Three branch and bound (B&B) approaches are compared which differ mainly in their branching strategies. One of them is the conventional B&B approach called the forward approach, and the other two are referred to as the backward and the double-sided approaches, respectively. To obtain an upper bound, a flowshop heuristic (FSH1) is employed and is subjected to 2-opt and 3-opt. Lower bounds for each approach are developed. In each case, the lower bound is taken as the weighted sum of the lower bounds for the average flowtime and for the makespan. A computational study is performed to evaluate the three different B&B approaches on a testbed consisting of 30 problems each for n = 10, n = 14, and n = 18, and each one of these problems is solved for five different levels of the weighting factor. An analysis into the resulting efficient points is also included. An improved version of FSH1 is developed and both heuristics are subjected to extensive numerical experimentation.
