Decision CPM: Network Reduction and Solution

The Decision Critical Path Method (DCPM) applies to problems having a discrete time-cost tradeoff and including the possibility of interdependency constraints between the discrete job alternatives. Previously, it has been formulated as an integer-programming problem and solved by integer programming or by heuristic techniques. This paper shows that a variant of the usual critical path method may be used to reduce DCPM networks to equivalent networks containing only decision nodes and maximal distances between them. This operation, along with feasibility tests on the interdependency constraints, allows substantial simplification. A branch-and-bound method is then developed to solve the reduced problem.     

Lagrangian-relaxation-based solution procedures for a multiproduct capacitated facility location problem with choice of facility type

This paper presents exact and heuristic solution procedures for a multiproduct capacitated facility location (MPCFL) problem in which the demand for a number of different product families must be supplied from a set of facility sites, and each site offers a choice of facility types exhibiting different capacities. MPCFL generalizes both the uncapacitated (or simple) facility location (UFL) problem and the pure-integer capacitated facility location problem. We define a branch-and-bound algorithm for MPCFL that utilizes bounds formed by a Lagrangian relaxation of MPCFL which decomposes the problem into UFL subproblems and easily solvable 0-1 knapsack subproblems. The UFL subproblems are solved by the dual-based procedure of Erlenkotter. We also present a subgradient optimization-Lagrangian relaxation-based heuristic for MPCFL. Computational experience with the algorithm and heuristic are reported. The MPCFL heuristic is seen to be extremely effective, generating solutions to the test problems that are on average within 2% of optimality, and the branch-and-bound algorithm is successful in solving all of the test problems to optimality.     

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.     

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.     

Maximizing total job value on a single machine with job selection

This paper describes a single-machine scheduling problem of maximizing total job value with a machine availability constraint. The value of each job decreases over time in a stepwise fashion. Several solution properties of the problem are developed. Based on the properties, a branch-and-bound algorithm and a heuristic algorithm are derived. These algorithms are evaluated in the computational study, and the results show that the heuristic algorithm provides effective solutions within short computation times.     

带准备时间的单机指数时间学习效应排序问题

研究带有准备时间的单机学习效应模型,其中工件加工时间具有指数时间学习效应,即工件的实际加工时间是已经排好的工件加工时间的指数函数。学习效应模型考虑工件的实际加工时间同时依赖于工件本身的加工时间和已加工工件的累计加工时间,目标函数为最小化总完工时间。这个问题是NP-难的,提出了一个数学规划模型来求解该问题的最优解。通过分析几个优势性质和下界,提出分支定界算法来求解此问题,并设计启发式算法改进分支定界算法的上界值。通过仿真实验验证了分支定界算法在求解质量和时间方面的有效性。     

Branch-and-bound and parallel computation: A historical note

This historical note summarizes what we believe to have been the first use of parallel processing to solve a combinatorial optimization problem by a branch-and-bound algorithm. In 1975, a branch-and-bound algorithm for the traveling salesman problem that used p parallel processors with shared memory was simulated on a single processor. The results show that the simultaneous exploration of several nodes of the search tree yields better feasible solutions earlier. This allows earlier pruning of branches and significantly reduces the number of nodes searched.     

No-wait flowshops with bicriteria of makespan and total completion time

We consider the m-machine no-wait flowshop scheduling problem with the objective of minimizing a weighted sum of makespan and total completion time. For the two-machine problem, we develop a dominance relation and embed it within a proposed branch-and-bound algorithm. For the m-machine problem, we propose a heuristic. Computational experiments show that the proposed heuristic outperforms the best existing multi-criteria heuristics and the best single criterion heuristics for makespan and total completion time. The efficiency of the dominance relation and branch-and-bound algorithm is also investigated and shown to be effective.     

Minimizing flow time in a flow-line manufacturing cell with family setup times

This paper considers the problem of scheduling part families and jobs within each part family in a flowline manufacturing cell with independent family setup times where parts (jobs) in each family are processed together. The objective is to minimize total flow time. A branch-and-bound algorithm capable of solving moderate sized problems is developed. Several heuristic algorithms are proposed and empirically evaluated as to their effectiveness and efficiency in finding optimal permutation schedules. These results show that several heuristic algorithms generate solutions that are better than those generated by an existing genetic algorithm.     

Minimizing total weighted completion time in a two-machine flow shop scheduling under simple linear deterioration

In this paper, we address a two-machine flow shop scheduling problem under simple linear deterioration. By a simple linear deterioration function, we mean that the processing time of a job is a simple linear function of its execution start time. The objective is to find a sequence that minimizes total weighted completion time. Optimal schedules are obtained for some special cases. For the general case, several dominance properties and two lower bounds are derived to speed up the elimination process of a branch-and-bound algorithm. A heuristic algorithm is also proposed to overcome the inefficiency of the branch-and-bound algorithm. Computational analysis on randomly generated problems is conducted to evaluate the branch-and-bound algorithm and heuristic algorithm.     

Generating constrained length personalized bicycle tours

In the context of recreational routing, the problem of finding a route which starts and ends in the same location (while achieving a length between specified upper and lower boundaries) is a common task, especially for tourists or cyclists who want to exercise. The topic of finding a tour between a specified starting and ending location while minimizing one or multiple criteria is well covered in literature. In contrast to this, the route planning task in which a pleasant tour with length between a maximum and a minimum boundary needs to be found is relatively underexplored. In this paper, we provide a formal definition of this problem, taking into account the existing literature on which route attributes influence cyclists in their route choice. We show that the resulting problem is NP-hard and devise a branch-and-bound algorithm that is able to provide a bound on the quality of the best solution in pseudo-polynomial time. Furthermore, we also create an efficient heuristic to tackle the problem and we compare the quality of the solutions that are generated by the heuristic with the bounds provided by the branch-and-bound algorithm. Also, we thoroughly discuss the complexity and running time of the heuristic.     

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.     

Reducing costs of backhaul networks for PCS networks using genetic algorithms

Designing cost-effective telecommunications networks often involves solving several challenging, interdependent combinatorial optimization problems simultaneously. For example, it may be necessary to select a least-cost subset of locations (network nodes) to serve as hubs where traffic is to be aggregated and switched; optimally assign other nodes to these hubs, meaning that the traffic entering the network at these nodes will be routed to the assigned hubs while respecting capacity constraints on the links; and optimally choose the types of links to be used in interconnecting the nodes and hubs based on the capacities and costs associated with each link type. Each of these three combinatorial optimization problems must be solved while taking into account its impacts on the other two. This paper introduces a genetic algorithm (GA) approach that has proved effective in designing networks for carrying personal communications services (PCS) traffic. The key innovation is to represent information about hub locations and their interconnections as two parts of a chromosome, so that solutions to both aspects of the problem evolve in parallel toward a globally optimal solution. This approach allows realistic problems that take 4–10 hours to solve via a more conventional branch-and-bound heuristic to be solved in 30–35 seconds. Applied to a real network design problem provided as a test case by Cox California PCS, the heuristics successfully identified a design 10% less expensive than the best previously known design. Cox California PCS has adopted the heuristic results and plans to incorporate network optimization in its future network designs and requests for proposals.     

A branch-and-bound algorithm for three-machine flowshop scheduling problem to minimize total completion time with separate setup times

In this paper, we address the three-machine flowshop scheduling problem. Setup times are considered separate from processing times, and the objective is to minimize total completion time. We show that the three-site distributed database scheduling problem can be modeled as a three-machine flowshop scheduling problem. A lower bound is developed and a dominance relation is established. Moreover, an upper bound is developed by using a three-phase hybrid heuristic algorithm. Furthermore, a branch-and-bound algorithm, incorporating the developed lower bound, dominance relation, and the upper bound is presented. Computational analysis on randomly generated problems is conducted to evaluate the lower and upper bounds, the dominance relation, and the branch-and-bound algorithm. The analysis shows the efficiency of the upper bound, and, hence, it can be used for larger size problems as a heuristic algorithm.     

The multiple-choice multi-period knapsack problem

This paper introduces the multiple-choice multi-period knapsack problem in the interface of multiple-choice programming and knapsack problems. We first examine the properties of the multiple-choice multi-period knapsack problem. A heuristic approach incorporating both primal and dual gradient methods is then developed to obtain a strong lower bound. Two branch-and-bound procedures for special-ordered-sets type 1 variables that incorporate, respectively, a special algorithm and the multiple-choice programming technique are developed to locate the optimal solution using the above lower bound as the initial solution. A computer program written in IBM's APL2 is developed to assess the quality of this lower bound and to evaluate the performance of these two branch-and-bound procedures.     

A multi-period network design problem for cellular telecommunication systems

Mathematical Programming models for multi-period network design problems, which arise in cellular telecommunication systems are presented. The underlying network topologies range from a simple star to complex multi-layer Steiner-like networks. Linear programming, Lagrangian relaxation, and branch-and-cut heuristics are proposed and a polynomial-bounded heuristic based on an interior point linear programming implementation is described. Extensive computational results are presented on a number of randomly generated problem sets and the performance of the heuristic(s) are compared with an optimal branch-and-bound algorithm.     

An Almost Optimal Heuristic for Preemptive C max Scheduling of Dependent Tasks on Parallel Identical Machines

We consider the problem of scheduling preemptable, dependent tasks on parallel, identical machines to minimize the makespan. The computational complexity of this problem remains open if the number of machines is fixed and larger than 2. The aim of this paper is to compare two heuristic algorithms on a basis of a computational experiment. The solutions generated by the heuristics are compared with optimal solutions obtained by a branch-and-bound algorithm. Computational results show that the heuristic based on node ordering finds optimal schedules for 99.9% of instances with the maximum relative deviation from optimum of 4.8%.     

Optimal and heuristic algorithms for multiproduct uncapacitated facility location

We consider a generalization of the classic uncapacitated facility location problem (UFLP) in which customers require multiple products. We call this the multiproduct uncapacitated facility location problem (MUFLP). In MUFLP, in addition to a fixed cost for opening a facility, a fixed cost is incurred for each product that a facility is equipped to handle. Also, an assignment cost is incurred for satisfying a customer's requirement for a particular product at a chosen facility. We describe a branch-and-bound algorithm for MUFLP. Lower bounds are obtained by solving a UFLP subproblem for each product using a dual ascent routine. We also describe a heuristic branch-and-bound procedure in which the solutions to the subproblems at a given node might not generate a true lower bound. To generate a feasible solution, a ‘superposition’ heuristic based on solving UFLP subproblems for each product, as well as a ‘drop’ heuristic that eliminates facilities and equipment from the solution in a step-by-step manner, are given. Computational results are reported.