A combined branch-and-bound and genetic algorithm based approach for a flowshop scheduling problem

In this paper, we study the application of a meta-heuristic to a two-machine flowshop scheduling problem. The meta-heuristic uses a branch-and-bound procedure to generate some information, which in turn is used to guide a genetic algorithm's search for optimal and near-optimal solutions. The criteria considered are makespan and average job flowtime. The problem has applications in flowshop environments where management is interested in reducing turn-around and job idle times simultaneously. We develop the combined branch-and-bound and genetic algorithm based procedure and two modified versions of it. Their performance is compared with that of three algorithms: pure branch-and-bound, pure genetic algorithm, and a heuristic. The results indicate that the combined approach and its modified versions are better than either of the pure strategies as well as the heuristic algorithm.     

Comparing an ACO algorithm with other heuristics for the single machine scheduling problem with sequence-dependent setup times

We compare several heuristics for solving a single machine scheduling problem. In the operating situation modelled, setup times are sequence-dependent and the objective is to minimize total tardiness. We describe an Ant Colony Optimization (ACO) algorithm having a new feature using look-ahead information in the transition rule. This feature shows an improvement in performance. A comparison with a genetic algorithm, a simulated annealing approach, a local search method and a branch-and-bound algorithm indicates that the ACO that we describe is competitive and has a certain advantage for larger problems.     

Single machine earliness and tardiness scheduling

We examine the problem of scheduling a given set of jobs on a single machine to minimize total early and tardy costs without considering machine idle time. We decompose the problem into two subproblems with a simpler structure. Then the lower bound of the problem is the sum of the lower bounds of two subproblems. A lower bound of each subproblem is obtained by Lagrangian relaxation. Rather than using the well-known subgradient optimization approach, we develop two efficient multiplier adjustment procedures with complexity O(nlog n) to solve two Lagrangian dual subproblems. A branch-and-bound algorithm based on the two efficient procedures is presented, and is used to solve problems with up to 50 jobs, hence doubling the size of problems that can be solved by existing branch-and-bound algorithms. We also propose a heuristic procedure based on the neighborhood search approach. The computational results for problems with up to 3 000 jobs show that the heuristic procedure performs much better than known heuristics for this problem in terms of both solution efficiency and quality. In addition, the results establish the effectiveness of the heuristic procedure in solving realistic problems to optimality or near optimality.     

A heterogeneous cooperative parallel search of branch-and-bound method and tabu search algorithm

In this study, we present a heterogeneous cooperative parallel search that integrates branch-and-bound method and tabu search algorithm. These two algorithms perform searches in parallel and cooperate by asynchronously exchanging information about the best solutions found and new initial solutions for tabu search. The rapid production of a good solution from the tabu search process provides the branch-and-bound process with a better feasible solution to accelerate the elimination of subproblems that do not contain an optimal solution. The new initial solution produced from the subproblem with a least-cost lower bound of the branch-and-bound method suggests the best potential area for tabu search to explore. We use a master-slave model to reduce the complexity of communication and enhance the performance of data exchange. A branch-and-bound process is used as the master process to control the exchange of information and the termination of computation. Several tabu search processes are executed simultaneously as the slave processes and cooperate by asynchronously exchanging information on the best solutions found and the new initial solutions by the master process of branch-and-bound. Based on the computation experiments of solving traveling salesman problems (TSP), the proposed heterogeneous parallel search algorithm outperforms a conventional parallel branch-and-bound method and a conventional parallel tabu search. We also present the computational results showing the efficiency of heterogeneous cooperative parallel search when we use more processors to accelerate search time. Thus, the proposed heterogeneous parallel search algorithm achieves linear accelerations.     

Branch-and-bound and weight-combination search algorithms for the total completion time problem with step-deteriorating jobs

In many real situations, it is found that if certain maintenance procedures fail to be completed prior to a pre-specified deterioration date, then the jobs will require extra time for successful completion. In this paper, a single-machine total completion time problem with step-deteriorating jobs is considered. A branch-and-bound method incorporated with several dominance properties and a lower bound is developed to derive the optimal solution for this problem. In addition, a weight-combination search algorithm is proposed to search for a near-optimal solution. Computational results indicate that the branch-and-bound algorithm can solve most of the problems with up to 24 jobs in a reasonable amount of time. Moreover, the proposed heuristic algorithm is accurate with mean deviations from the optimum value of less than 0.3%.     

A three-machine permutation flow-shop problem with minimum makespan on the second machine

In this paper, we consider a three-machine permutation flow-shop scheduling problem where the criterion is to minimize the total completion time without idle times subject to the minimum makespan on the second machine. This problem is NP-hard while each of the objective functions alone can be optimized in polynomial time. We develop a branch-and-bound algorithm with effective branching rules and dominance properties which help to reduce the search space. By our computational experiments, the branch-and-bound algorithm is comparable to a recent mixed integer programming solver and, for some kinds of problem instances, the branch-and-bound algorithm outperforms the solver. On the other hand, the computational result would indicate that the hierarchical scheduling problems are essentially hard in both theoretical and computational points of view.     

Global optimization for generalized geometric programming problems with discrete variables

Generalized geometric programming (GGP) problems occur frequently in engineering design and management, but most existing methods for solving GGP actually only consider continuous variables. This article presents a new branch-and-bound algorithm for globally solving GGP problems with discrete variables. For minimizing the problem, an equivalent monotonic optimization problem (P) with discrete variables is presented by exploiting the special structure of GGP. In the algorithm, the lower bounds are computed by solving ordinary linear programming problems that are derived via a linearization technique. In contrast to pure branch-and-bound methods, the algorithm can perform a domain reduction cut per iteration by using the monotonicity of problem (P), which can suppress the rapid growth of branching tree in the branch-and-bound search so that the performance of the algorithm is further improved. Computational results for several sample examples and small randomly generated problems are reported to vindicate our conclusions.     

Accelerating Branch-and-Bound through a Modeling Language Construct for Relaxation-Specific Constraints

In the tradition of modeling languages for optimization, a single model is passed to a solver for solution. In this paper, we extend BARON’s modeling language in order to facilitate the communication of problem-specific relaxation information from the modeler to the branch-and-bound solver. This effectively results into two models being passed from the modeling language to the solver. Three important application areas are identified and computational experiments are presented. In all cases, nonlinear constraints are provided only to the relaxation constructor in order to strengthen the lower bounding step of the algorithm without complicating the local search process. In the first application area, nonlinear constraints from the reformulation–linearization technique (RLT) are added to strengthen a problem formulation. This approach is illustrated for the pooling problem and computational results show that it results in a scheme that makes global optimization nearly as fast as local optimization for pooling problems from the literature. In the second application area, we communicate with the relaxation constructor the first-order optimality conditions for unconstrained global optimization problems. Computational experiments with polynomial programs demonstrate that this approach leads to a significant reduction of the size of the branch-and-bound search tree. In the third application, problem-specific nonlinear optimality conditions for the satisfiability problem are used to strengthen the lower bounding step and are found to significantly expedite the branch-and-bound algorithm when applied to a nonlinear formulation of this problem.     

Crane scheduling with non-crossing constraint

In this paper, we examine crane scheduling for ports. This important component of port operations management is studied when the non-crossing spatial constraint, which is common to crane operations, is considered. We assume that ships can be divided into holds and that cranes can move from hold to hold but jobs are not pre-emptive, so that only one crane can work on one hold or job to complete it. Our objective is to minimize the latest completion time for all jobs. We formulate this problem as an integer programming problem. We provide the proof that this problem is NP-complete and design a branch-and-bound algorithm to obtain optimal solutions. A simulated annealing meta-heuristic with effective neighbourhood search is designed to find good solutions in larger size instances. The elaborate experimental results show that the branch-and-bound algorithm runs much faster than CPLEX and the simulated annealing approach can obtain near optimal solutions for instances of various sizes.     

Improved Bounds for the Range of Lateness on a Single Machine

In a recent article, Gupta and Sen have developed an algorithm to minimize the range of lateness on a single machine. The algorithm is based on the branch-and-bound approach suggested by Townsend for single-machine problems with quadratic penalty functions of completion times. In this paper, a simple general result for regular composition of cost functions is presented, application of which improves the Gupta and Sen procedure.     

Application of an optimization problem in Max-Plus algebra to scheduling problems

The problem tackled in this paper deals with products of a finite number of triangular matrices in Max-Plus algebra, and more precisely with an optimization problem related to the product order. We propose a polynomial time optimization algorithm for 2×2 matrices products. We show that the problem under consideration generalizes numerous scheduling problems, like single machine problems or two-machine flow shop problems. Then, we show that for 3×3 matrices, the problem is NP-hard and we propose a branch-and-bound algorithm, lower bounds and upper bounds to solve it. We show that an important number of results in the literature can be obtained by solving the presented problem, which is a generalization of single machine problems, two- and three-machine flow shop scheduling problems. The branch-and-bound algorithm is tested in the general case and for a particular case and some computational experiments are presented and discussed.     

A branch-and-bound algorithm with fuzzy inference for a permutation flowshop scheduling problem

This paper considers an m-machine permutation flowshop scheduling problem of minimizing the makespan. This classical scheduling problem is still important in modern manufacturing systems, and is well known to be intractable (i.e., NP-hard). In fact branch-and-bound algorithms developed so far for this problem have not come to solve large scale problem instances with over a hundred jobs. In order to improve the performance of branch-and-bound algorithms this paper proposes a new dominance relation by which the search load could be reduced, and notices that it is based on a sufficient precondition. This suggests that the dominance relation holds with high possibility even if the precondition approximately holds, thus being more realistic. The branch-and-bound algorithm proposed here takes advantage of this possibility for obtaining an optimal solution as early as possible in the branch-and-bound search. For this purpose this paper utilizes membership functions in the context of the fuzzy inference. Extensive numerical experiments that were executed through Monte Carlo simulations and benchmark tests show that the developed branch-and-bound algorithm can solve 3-machine problem instances with up to 1000 jobs with probability of over 99%, and 4-machine ones with up to 900 jobs with over 97%.     

An Algorithm for Minimizing the Range of Lateness on a Single Machine

This paper considers the problem of minimizing the range of lateness on a single machine. All the algorithms in the literature for solving this problem are based on the branch-and-bound approach, which has an exponential time complexity. In this paper, we demonstrate that this problem can actually be solved in pseudo-polynomial time, and develop such an algorithm. Computational performance of this algorithm on problems with various sizes is provided.     

Minimizing total flow time in the single-machine scheduling problem with periodic maintenance

This paper deals with a single-machine scheduling problem with limited machine availability. The limited availability of machine results from periodic maintenance activities. In our research, a periodic maintenance schedule consists of several maintenance periods. Each maintenance period is scheduled after a periodic time interval. The objective is to find a schedule that minimizes the total flow time subject to periodic maintenance and nonresumable jobs. Some important theorems are proved for the problem. A branch-and-bound algorithm that utilizes several theorems is proposed to find the optimal schedule. We also develop a heuristic to solve large sized problems. In this paper, computational results show that the proposed heuristic is highly accurate and efficient.     

Scheduling preemptive open shops to minimize total tardiness

This article considers the problem of scheduling preemptive open shops to minimize total tardiness. The problem is known to be NP-hard. An efficient constructive heuristic is developed for solving large-sized problems. A branch-and-bound algorithm that incorporates a lower bound scheme based on the solution of an assignment problem as well as various dominance rules are presented for solving medium-sized problems. Computational results for the 2-machine case are reported. The branch-and-bound algorithm can handle problems of up to 30 jobs in size within a reasonable amount of time. The solution obtained by the heuristic has an average deviation of less than 2% from the optimal value, while the initial lower bound has an average deviation of less than 11% from the optimal value. Moreover, the heuristic finds approved optimal solutions for over 65% of the problems actually solved.     

Single Machine Scheduling and Selection to Minimize Total Flow Time with Minimum Number Tardy

Emmons considered the problem of sequencing N jobs on a single machine to minimize total flow time with the minimum number of tardy jobs. He proposed an effective branch-and-bound algorithm for this problem. In this paper, we show that Emmons' algorithm can be extended to a more difficult scheduling problem which includes an optimal selection of jobs as well.     

Branch and probability bound methods in multi-objective optimization

An approach to non-convex multi-objective optimization problems is considered where only the values of objective functions are required by the algorithm. The proposed approach is a generalization of the probabilistic branch-and-bound approach well applicable to complicated problems of single-objective global optimization. In the present paper the concept of probabilistic branch-and-bound based multi-objective optimization algorithms is discussed, and some illustrations are presented.     

A Constraint Programming Framework for Local Search Methods

We propose in this paper a novel integration of local search algorithms within a constraint programming framework for combinatorial optimization problems, in an attempt to gain both the efficiency of local search methods and the flexibility of constraint programming while maintaining a clear separation between the constraints of the problem and the actual search procedure. Each neighborhood exploration is performed by branch-and-bound search, whose potential pruning capabilities open the door to more elaborate local moves, which could lead to even better approximate results. Two illustrations of this framework are provided, including computational results for the traveling salesman problem with time windows. These results indicate that it is one order of magnitude faster than the customary constraint programming approach to local search and that it is competitive with a specialized local search algorithm.     

An efficient computational method for a stochastic dynamic lot-sizing problem under service-level constraints

We provide an efficient computational approach to solve the mixed integer programming (MIP) model developed by Tarim and Kingsman [8] for solving a stochastic lot-sizing problem with service level constraints under the static-dynamic uncertainty strategy. The effectiveness of the proposed method hinges on three novelties: (i) the proposed relaxation is computationally efficient and provides an optimal solution most of the time, (ii) if the relaxation produces an infeasible solution, then this solution yields a tight lower bound for the optimal cost, and (iii) it can be modified easily to obtain a feasible solution, which yields an upper bound. In case of infeasibility, the relaxation approach is implemented at each node of the search tree in a branch-and-bound procedure to efficiently search for an optimal solution. Extensive numerical tests show that our method dominates the MIP solution approach and can handle real-life size problems in trivial time.     

Minimizing the makespan in a two-machine cross-docking flow shop problem

This paper studies a two-machine cross-docking flow shop scheduling problem in which a job at the second machine can be processed only after the processing of some jobs at the first machine has been completed. The objective is to minimize the makespan. We first show that the problem is strongly NP-hard. Some polynomially solvable special cases are provided. We then develop a polynomial approximation algorithm with an error-bound analysis. A branch-and-bound algorithm is also constructed. Computational results show that the branch-and-bound algorithm can optimally solve problems with up to 60 jobs within a reasonable amount of time.