A Branch-and-Bound Algorithm for Flow Shop Scheduling Problems

This article is concerned with the solution of the flow shop scheduling problem in which all jobs have the same machine ordering. A branch-and-bound algorithm is developed for finding the sequence of J jobs to be processed on M machines which minimizes the schedule time. Thib algorithm consists of branching and bounding processes, but without the backtracking process which guarantees optimality. The procedure employed is that in constructing a subset of feasible sequences, a node representing a partial sequence is branched. Selection of the node depends on the lower-bound concept as a decision rule. This lower bound is based on resolving the conflict of jobs on the last machine. By using this algorithm, the number of explored nodes is considerably reduced and, hence, the computational effort involved in obtaining an optimal or near-optimal solution is decreased. High quality of solutions is obtained. Computationally, this algorithm extends the size of problems that can reasonably be solved.     

Optimal flow path design of unidirectional AGV systems

This paper describes an alternative formulation of the AGV flow path layout (FPL) problem which was first formulated by Gaskins and Tanchoco (1987) as a zero-one integer programming problem. A computationally efficient procedure is proposed which is based on the branch-and-bound technique. An algorithm for satisfying the reachability condition for nodes in the AGV flow path network is also presented. A simple illustrative example is discussed to demonstrate the procedure, and a more complex problem is also given.     

A branch-and-bound algorithm for minimizing the sum of maximum earliness and tardiness with unequal release times

This article addresses the problem of minimizing the sum of maximum earliness and tardiness on a single machine with unequal release times. It is proven that this problem is NP-hard in the strong sense and a branch-and-bound algorithm is developed as an exact method. In the proposed algorithm, modified dispatching rules based on different release times are proposed as the upper bound, while a procedure considering preemption assumption is used to obtain a good lower bound. Also, dominance rules based on no unforced idle time, adjacent pairwise interchanges in the base problem, and job blocks are used to fathom the nodes. In order to evaluate the efficiency of the proposed algorithm, 4,860 instances were randomly generated, varying from 7 to 1,000 jobs. It is shown that the branch-and-bound algorithm was capable of optimally solving 94.1% of the instances, showing its efficiency in solving all problem sizes.     

Solution algorithms for the number of tardy jobs minimisation scheduling with a time-dependent learning effect

This paper deals with a single-machine scheduling problem with a time-dependent learning effect. The goal is to determine the job sequence that minimise the number of tardy jobs. Two dominance properties, two heuristic algorithms and a lower bound to speed up the search process of the branch-and-bound algorithm are proposed. Computational experiments show that the branch-and-bound algorithm can solve instances up to 18 jobs in a reasonable amount of time, and the proposed heuristic algorithm MFLA performs effectively and efficiently     

Optimal solution for the flow path design problem of a balanced unidirectional AGV system

An optimal flow path layout (FPL) design method is introduced as a handy tool for an automated guided vehicle (AGV) system planing stage. The problem is analysed and formulated by linear mixed-integer programming. A procedure based on the branch-and-bound depth-first search technique is proposed to solve the FPL problem. The procedure is implemented as an efficient computer program and yields an optimal solution in a small number of iterations. Using the transportation model for calculating the required and optimal flow of empty vehicles, system balance is achieved. Finally, two examples are given. A simple illustrative example is discussed to demonstrate the procedure, and a realistic FPL problem with 23 nodes, 66 arcs and nine pick-up/delivery stations is solved.     

U-OPT: An analysis of exact U-shaped line balancing procedures

The U-shaped assembly line-balancing problem can be solved using optimization procedures or algorithms, including branch-and-bound procedures. This paper considers design elements that should be included in these solution methods for solving the U-shaped assembly line-balancing problem. New solution procedures are proposed and compared experimentally with several existing procedures using a variety of problem sets from the literature. The results show that the substantial improvement in the efficacy of the new solution procedures over existing methods is due primarily to the newly developed 'Paired Tasks' lower bound. Results also show the relative importance of various design elements comprising a branch-and-bound procedure.     

Single-track multi-hoist scheduling problem: a collision-free resolution based on a branch-and-bound approach

An analytical mathematical model and a branch-and-bound algorithm for single-track cyclic multi-hoist scheduling problems are proposed. The objective is to minimize the cycle time for a given number of hoists. The collision-free single-track constraints are first formulated as disjunctive inequalities. It is then shown that this formulation is a very strict and necessary condition. To be a sufficient and necessary one, two additional properties, like collision-checking rules, must hold in optimal solutions. It is proved that a solution violating these two properties due to their relaxation is always dominated by a collision-free one. Therefore, these two properties are relaxed in the branch-and-bound algorithm. The computation of lower bounds in the branch-and-bound algorithm requires the solution of a specific linear programming problem, which can be solved by using a graph-based polynomial algorithm. Computational results with both benchmark and randomly generated test instances are presented.     

An optimisation model and its effective beam search heuristics for floor-storage warehousing systems

This paper presents an optimisation model and its effective solution technique using beam search heuristic for floor-storage warehousing systems. For a floor-storage system, storage can be accessed from the top of stacks only. The objective is to minimise the number of re-handling operations by optimally determining the storage location and by grouping products for each customer that fit a given sequence for receiving and retrieving operations. An integer programming model is formulated and an approximate solution technique based on the beam search method is proposed to solve the problem by incorporating effective heuristics to reduce the search space using future receiving and retrieving requests. The effectiveness of the proposed method is demonstrated for industrial warehousing problems in a steel plant with 58 storage areas involving more than 3000 retrieving operations. The proposed solution method is shown to be more efficient than the traditional branch-and-bound method for solving integer programming problems.     

A branch-and-bound approach for machine selection in just-in-time manufacturing systems

Equipment selection issues are very important in the early stages of implementation of just-in-time (JIT) manufacturing systems. This paper addresses the problem of determining the number of machines for each stage of a JIT system by minimizing production, imbalance and investment costs. The problem is modelled as a mixed-integer nonlinear optimization program and a branch-and-bound algorithm is developed for its solution. This algorithm guarantees the global optimum of the problem and is enhanced by simple, yet very effective, upper bounding heuristics. The solutions obtained by the developed branch-and-bound approach are compared to solutions that have appeared in the literature using heuristic approaches. The comparisons indicate that the proposed algorithm leads to significant economic savings, averaging 17% on a set of problems from the literature. The paper also considers the application of the algorithm to large-scale, industrially-relevant, problems with up to 10 stages and 200 products. Even for the largest of these problems, the search for the integer optimum requires modest computational times. This demonstrates the potential practical impact of the proposed methodology.     

Constructive heuristic algorithm in branch-and-bound structure applied to transmission network expansion planning

A constructive heuristic algorithm to solve the transmission system expansion planning problem is proposed with the aim of circumventing some critical problems of classical heuristic algorithms that employ relaxed mathematical models to calculate a sensitivity index that guides the circuit additions. The proposed heuristic algorithm is in a branch-and-bound algorithm structure, which can be used with any planning model, such as Transportation model, DC model, AC model or Hybrid models. Tests of the proposed algorithm are presented on real Brazilian systems     

Scheduling parallel machines to minimize weighted flowtime with family set-up times

We describe and evaluate several branch-and-bound algorithms for an identical parallel machine scheduling problem with family set-up times and an objective of minimizing total weighted flowtime. The algorithms differ by choice of lower bound method. Computational results suggest conditions favourable to a particular algorithm as well as the range of problem sizes that can be optimally solved in reasonable CPU time.     

Extensions of the Multi-Period Facility Phase-Out Model: New Procedures and Application to a Phase-In/Phase-Out Problem

This paper extends the multi-period facility phase-out model of Roodman and Schwarz in two ways: First, the branch-and-bound procedure is improved by the incorporation of two new lower bounds, which are both easier to obtain and more powerful than those originally proposed, and the addition of two new simplifications. Second, the model itself is generalized to solve a phase-in/phase-out problem. The improved branch-and-bound procedure is directly applicable to the static facility location models of Efroymson and Ray and Khumawala, and has consistently solved sample static problems faster than the methods proposed by these authors.     

Integer programming approach to the printed circuit board grouping problem

A printed circuit board (PCB) grouping problem arising from the electronics industry is considered. Given a surface-mounting device with a number of component feeders and several types of PCBs to be produced, the problem is how to group the PCBs so that the total set-up time for component feeders is minimized. The problem is formulated as an integer-programming problem and a column generation approach is proposed to solve it. In this approach, the original problem is decomposed into a master problem and a column-generation subproblem. Starting with a few columns in the master problem, new columns are generated successively by solving the subproblem optimally. To solve the subproblem, a branch-and-cut approach is used. To solve the master problem, a branch-and-bound algorithm is used with the generated columns. However, a branching strategy is also proposed that maintains consistency in the column-generation procedure after branching. Computational experiments show that the solution approach gives high-quality solutions in reasonable computing time.     

Working time constraints in operational fixed job scheduling

In this study we consider the operational fixed job scheduling problem under working time limitations. The problem has several practical implications in both production and service operations; however the relevant research is scarce. We analyse pre-emptive and non pre-emptive versions of the problem and its special cases. We provide polynomial-time algorithms for some special cases. We show that the non pre-emptive jobs problem is strongly NP-hard, and propose a branch-and-bound algorithm that employs efficient bounding procedures and dominance properties. We conduct a numerical experiment to observe the effects of parameters on the quality of the solution. The results of our computational tests for the branch-and-bound algorithm reveal that our algorithm can solve the instances with up to 100 jobs in reasonable times. To the best of our knowledge our branch-and-bound algorithm is the first optimisation attempt to solve the problem.     

Group scheduling with deteriorating jobs and allotted resource under limited resource availability constraint

This study considers a single machine group scheduling problem with deteriorating jobs and resource allocation (controllable processing times). The objective is to have the resource availability limited within a given range, and to minimize the maximum completion time (i.e. the makespan). For two special cases, it is proved that the problem can be solved in polynomial time. For the general case, an heuristic algorithm and a branch-and-bound algorithm are proposed. Computational results show that the proposed heuristic algorithm is generally effective.     

Scheduling a Single Machine to Minimize the Weighted Number of Tardy Jobs

In this paper the problem of scheduling jobs on a single machine to minimize the weighted number of tardy jobs is examined. It contains the framework for a new branch-and-bound procedure as well as the first extensive computational study of the problem. Results indicate that large problems, e.g. 50 jobs, can be solved in just a few seconds of computer time. Further, the computational results provide insight into how various problem parameters affect the solution difficulty of particular problems.     

Response surface-based robust parameter design optimization with both qualitative and quantitative variables

The response surface-based robust parameter design, with its extensive use of optimization techniques and statistical tools, is known as an effective engineering design methodology for improving production processes, when input variables are quantitative on a continuous scale. In many engineering settings, however, there are situations where both qualitative and quantitative variables are considered. In such situations, traditional response surface designs may not be effective. To rectify this problem, this article lays out a foundation by embedding those input variables into a factorial design with pseudo-centre points. A 0–1 mixed-integer nonlinear programming model is then developed and the solutions found using three optimization tools, namely the outer approximation method, the branch-and-bound technique and the hybrid branch-and-cut algorithm, are compared with traditional counterparts. The numerical example shows that the proposed models result in better robust parameter design solutions than the traditional models.     

Minimizing the total completion time in a two-machine flowshop problem with time delays

This article proposes to solve the problem of minimizing the total completion time in a two-machine permutation flowshop environment in which time delays between the machines are considered. For this purpose, an enumeration algorithm based on the branch-and-bound framework is developed, which includes new lower and upper bounds as well as dominance rules. The computational study shows that problems with up to 40 jobs can be solved in a reasonable amount of time.     

A capacitated vehicle routing problem for just-in-time delivery

This paper focuses on the formulation and solution of the problem of planning vehicle routes for material delivery within the premises of a plant working under a just-in-time production system. The unique characteristic of this problem is that the quantity to be delivered at each of the demand nodes is a function of the route taken by the vehicle assigned to serve that node. The problem is modeled by adding a non-linear capacity constraint to the standard vehicle routing model, such that vehicle idle times and inventories at the customer locations are minimized. A heuristic solution procedure is outlined, and the formulation of a lower-bound relaxation is suggested. The performance of the heuristic solution procedure is evaluated in comparison to the lower-bound relaxation, and the heuristic procedure is shown to provide generally good results.     

Optimal solution methods for the minimum-backtracking row layout problem

The problem of finding a reordering of the rows (and, simultaneously, the columns) of square matrices has important applications in the areas of combinatorial data analysis, economics and engineering. One such application is the Minimum-Backtracking Row Layout Problem (MBRLP), which involves the sequencing of workstations in an automated assembly line so as to minimize the total backtracking distance. Dynamic programming and integer programming have previously been proposed as optimal solution methods for the MBRLP; however, the latter method was limited to the case of equal distances between positions in the sequence. We demonstrate that the previously suggested integer programming approach for equidistant MBRLPs can produce infeasible solutions, and develop and test a plausible integer programming model for its replacement. We also present an optimal branch-and-bound procedure for MBRLP that requires far less memory storage than dynamic programming. Our experimental tests revealed that both dynamic programming and the branch-and-bound algorithm efficiently provided optimal solutions to MBRLPs with 25 or fewer workstations, and that neither method was superior in all cases. However, the branch-and-bound algorithm was appreciably faster than dynamic programming for some data conditions, and can be used for problems where computer RAM limitations preclude dynamic programming implementation.