^{1}

^{*}

^{1}

^{*}

^{2}

^{*}

The general m-machine permutation flowshop problem with the total flow-time objective is known to be NP-hard for m ≥ 2. The only practical method for finding optimal solutions has been branch-and-bound algorithms. In this paper, we present an improved sequential algorithm which is based on a strict alternation of Generation and Exploration execution modes as well as Depth-First/Best-First hybrid strategies. The experimental results show that the proposed scheme exhibits improved performance compared with the algorithm in [1]. More importantly, our method can be easily extended and implemented with lightweight threads to speed up the execution times. Good speedups can be obtained on shared-memory multicore systems.

In the permutation flowshop problem, each of n jobs has to be processed on machines 1···m in that order. The processing times of each job on each machine are known. At any time, each machine can process at most one job and each job can be processed on at most one machine. Once the processing of a job on a machine has started, it must be completed without interruption. The usual objectives are the minimization of the make-span, flow time, tardiness, lateness, and the number of jobs late. For a review of the general flowshop problem, see [

Schedules where each job must be processed in the same order at every machine are called permutation schedules. When m ≤ 2, the restriction to permutation schedules is harmless; however, when m > 3, there may exist a schedule whose total flow is strictly less than the total flow of any permutation schedule. Finding such a schedule among (n!)^{m} possible schedules is often computationally impractical [

The general m-machine permutation flowshop problem with the total flow-time objective is known to be NPhard for m ≥ 2. Flow time measures the time a job stays in the system. Minimizing it amounts to maximizing the utilization of resources. Because it is highly unlikely to develop a polynomial algorithm to solve the problem, researchers have focused on the use of branch and bound algorithms to find an optimal schedule for the problem.

In this paper, we propose an improved branch and bound algorithm which is based on the existing algorithm [

Considering the lengthy process in the search for lower bounds, the use of parallelism has a better chance of speeding up the execution of the algorithm and has emerged as an attractive way of solving larger problems [

Sequential and parallel branch-and-bound algorithms have been widely studied over the past several decades. Regarding the permutation flowshop problems, the paper [

The paper [

If there is no master used for generating tasks, the decomposition of the problem tree relies on all cooperating processes. A decomposition method for parallel depthfirst search can be found in [

An alternative way of dealing with permutation flowshop problems is to develop effective heuristics to obtain approximate solutions. The evaluation and comparison of several heuristic approaches for permutation flowshops can be found in [15,16]. Recently, metaheuristics, such as genetic algorithms, simulated annealing, tabu search, etc., have been successfully applied to many combinatorial optimization problems. See [17,18] for reviews of the literature on metaheuristics.

Assume that there are n jobs which will be processed in the same order by m machines. Consider the search tree where root node represents the null schedule. Every other node represents a partial schedule, indicating that job occupies the jth position on each machine, for 1 ≤ j ≤ s, where s is the number of jobs in the partial schedule and 1 ≤ s ≤ n. Any permutation of the set of unscheduled jobs defines a complete schedule. By placing any unscheduled job i in position s+1, we produce a descendant node.

Consider our lower bound on the total flow time at node. Let denote the total flow time for jobs in the partial schedule and let U be the set of jobs that are not included in the partial schedule. Our lower bound is based on estimates of the earliest possible start time for any job in U assigned to position t, where s + 1 ≤ t ≤ n. The idea behind these estimates is that a job can be processed at a machine only when both the job and the machine are ready. Assume that p_{jk} denotes the processing time of job j on machine k and the partial processing time of job j on machines u···v is represented by, our lower bound LB on the total flow time at node is computed as follows:

,

where E_{tk} is an underestimate of the earliest start time of the t job on machine k, for t ≥ s + 1. The detail of computing E_{tk} can be found in [

Note that some partial sequences can be pruned without checking lower bounds if they are dominated by others. Specifically, let s_{1} and s_{2} be two partial schedules for the same set of jobs S. We say that s_{1} dominates s_{2}, if for every permutation s of the jobs in N − S. If the previous inequality is strict, we say that s_{1} strictly dominates s_{2}. Hence, during the branch and bound searching process, the partial schedule s_{2} can be pruned.

A branch and bound algorithm has been developed to solve the m-machine permutation flowshop problem [^{*} from an initial feasible solution. The search strategy incorporates a dominance and a best bound rule. Given the current node, let U_{r} denote the set of all jobs not in the set , and for each, let denote the lower bound for node s_{r}j. Also, let and. (Note that si º s_{r}.) For each, our algorithm dictates the following. If node ij has not been previously fathomed, use the dominance test mentioned earlier to determine whether sji strictly dominates sij. If so, then fathom sij and assign to it the lower bound; otherwise, compute a lower bound for sij. After calculating all of these lower bounds, , branch on the job j with the smallest lower bound. When the search reaches a leaf node, a complete schedule is found. If the leaf node’s lower bound value is less than the global upper bound Z^{*}, the value and the schedule will replace the current Z^{*} and s^{*}, respectively.

Our improved branch and bound algorithm is based on the existing algorithm in [

In general, the algorithm runs by strictly alternating between the Generation and Exploration modes. When the upper tree has been traversed completely, i.e. no new node will be generated into the work pool, all of the remaining nodes in the work pool will be explored based on their lower bound values. Note that the pool size should be reasonable large enough to accommodate subtree candidates as many as possible. The nodes with smaller lower bound values at level i will have higher chances to be explored and hence the optimal solution could be found earlier.