Single machine scheduling to minimize total weighted earliness subject to minimal number of tardy jobs

Motivated by just-in-time manufacturing, we consider a single machine scheduling problem with dual criteria, i.e., the minimization of the total weighted earliness subject to minimum number of tardy jobs. We discuss several dominance properties of optimal solutions. We then develop a heuristic algorithm with time complexity O(n³) and a branch and bound algorithm to solve the problem. The computational experiments show that the heuristic algorithm is effective in terms of solution quality in many instances while the branch and bound algorithm is efficient for medium-size problems.     

Algorithms for common due-date assignment and sequencing on a single machine with sequence-dependent setup times

This paper focuses on the single machine sequencing and common due-date assignment problem for the objective of minimizing the sum of the penalties associated with earliness, tardiness and due-date assignment. Unlike the previous research articles on this class of scheduling problem, we consider sequence-dependent setup times that make the problem much more difficult. To solve the problem, a branch and bound algorithm, which incorporates the method to obtain lower and upper bounds as well as a dominance property to reduce the search space, is suggested that gives the optimal solutions for small-sized instances. Heuristic algorithms are suggested to obtain solutions for large-sized problems within a reasonable computation time. The performances of both the optimal and heuristic algorithms, in computational experiments on randomly generated test instances, are reported.     

A hybrid tabu search/branch & bound approach to solving the generalized assignment problem

A new approach for solving the generalized assignment problem (GAP) is proposed that combines the exact branch & bound approach with the heuristic strategy of tabu search (TS) to produce a hybrid algorithm for solving GAP. The algorithm described uses commercial software to solve sub-problems generated by the TS guiding strategy. The TS approach makes use of the concept of referent domain optimisation and introduces novel add/drop strategies. In addition, the linear programming relaxation of GAP that forms part of the branch & bound approach is itself helpful in suggesting which variables might take binary values. Computational results on benchmark test instances are presented and compared with results obtained by the standard branch & bound approach and also several other heuristic approaches from the literature. The results show the new algorithm performs competitively against the alternatives and is able to find some new best solutions for several benchmark instances.     

Branch and bound based solution algorithms for the budget constrained discrete time/cost trade-off problem

The time/cost trade-off models in project management aim to reduce the project completion time by putting extra resources on activity durations. The budget problem in discrete time/cost trade-off scheduling selects a time/cost mode for each activity so as to minimize the project completion time without exceeding the available budget. There may be alternative modes that solve the budget problem optimally and each solution may have a different total cost value. In this study we consider the budget problem and aim to find the minimum cost solution among the minimum project completion time solutions. We analyse the structure of the problem together with its linear programming relaxation and derive some mechanisms for reducing the problem size. We solve the reduced problem by branch and bound based optimization and heuristic algorithms. We find that our branch and bound algorithm finds optimal solutions for medium-sized problem instances in reasonable times and the heuristic algorithms produce high quality solutions very quickly.     

BBPH: Using progressive hedging within branch and bound to solve multi-stage stochastic mixed integer programs

Progressive hedging, though an effective heuristic for solving stochastic mixed integer programs (SMIPs), is not guaranteed to converge in this case. Here, we describe BBPH, a branch and bound algorithm that uses PH at each node in the search tree such that, given sufficient time, it will always converge to a globally optimal solution. In addition to providing a theoretically convergent “wrapper” for PH applied to SMIPs, computational results demonstrate that for some difficult problem instances branch and bound can find improved solutions after exploring only a few nodes.     

Minimizing total tardiness on a two-machine re-entrant flowshop

We present a branch and bound algorithm for a two-machine re-entrant flowshop scheduling problem with the objective of minimizing total tardiness. In the re-entrant flowshop considered here, all jobs must be processed twice on each machine, that is, each job should be processed on machine 1, machine 2 and then machine 1 and machine 2. By regarding a job as a pair of sub-jobs, each of which represents a pass through the two machines, we develop dominance properties, a lower bound and heuristic algorithms for the problem, and use these to develop a branch and bound algorithm. For evaluation of the performance of the algorithms, computational experiments are performed on randomly generated test problems and results are reported. Results of the experiments show that the suggested branch and bound algorithm can solve problems with up to 20 sub-jobs in a reasonable amount of CPU time, and the average percentage gap of the heuristic solutions is about 13%.     

A branch and bound algorithm for determining locations of long-term care facilities

This paper focuses on the problem of determining locations for long-term care facilities with the objective of balancing the numbers of patients assigned to the facilities. We present a branch and bound algorithm by developing dominance properties, a lower bounding scheme and a heuristic algorithm for obtaining an upper bound for the problem. For evaluation of the suggested branch and bound algorithm, computational experiments are performed on a number of test problems. Results of the experiments show that the suggested algorithm gives optimal solutions of problems of practical sizes in a reasonable amount of computation time.     

Solving real-world sized container pre-marshalling problems with an iterative deepening branch-and-bound algorithm

Container terminals around the world regularly re-sort the containers they store according to their retrieval times in a process called pre-marshalling, thus ensuring containers are efficiently transferred through the terminal. State-of-the-art algorithms struggle to find optimal solutions for real-world sized pre-marshalling problems. To this end, we introduce an improved exact algorithm using an iterative deepening branch and bound search, including a novel lower bound computation, a new branching heuristic, new dominance rule and a new greedy partial solution completion heuristic. Our approach finds optimal solutions for 161 more instances than the state-of-the-art algorithm on two well known, difficult pre-marshalling datasets, and solves all instances in three other datasets in just several seconds. Furthermore, we find optimal solutions for a majority of real-world sized instances, and feasible solutions with very low relaxation gaps on those instances where no optimal could be found.     

Genetic Algorithm for Network Cost Minimization Using Threshold Based Discounting

We present a genetic algorithm for heuristically solving a cost minimization problem applied to communication networks with threshold based discounting. The network model assumes that every two nodes can communicate and offers incentives to combine of from different sources. Namely, there is a prescribed threshold on every link, and if the total of on a link is greater than the threshold, the cost of this of is discounted by a factor. A heuristic algorithm based on genetic strategy is developed and applied to a benchmark set of problems. The results are compared with former branch and bound results using the CPLEX(r)solver. For larger data instances we were able to obtain improved solutions using less CPU time, confirming the effectiveness of our heuristic approach.     

A branch and bound algorithm for disassembly scheduling with assembly product structure

This paper considers a production planning problem in disassembly systems, which is the problem of determining the quantity and timing of disassembling end-of-use/life products in order to satisfy the demand of their parts or components over a planning horizon. The case of single product type without parts commonality is considered for the objective of minimizing the sum of setup and inventory holding costs. To show the complexity of the problem, we prove that the problem is NP-hard. Then, after deriving the properties of optimal solutions, a branch and bound algorithm is suggested that incorporates the Lagrangean relaxation-based upper and lower bounds. Computational experiments are performed on a number of randomly generated problems and the test results indicate that the branch and bound algorithm can give optimal solutions up to moderate-sized problems in a reasonable computation time. A Lagrangean heuristic for a viable alternative for large-sized problems is also suggested and compared with the existing heuristics to show its effectiveness.     

A Dynamic Domain Contraction Algorithm for Nonconvex Piecewise Linear Network Flow Problems*

We consider the Nonconvex Piecewise Linear Network Flow Problem (NPLNFP) which is known to be -hard. Although exact methods such as branch and bound have been developed to solve the NPLNFP, their computational requirements increase exponentially with the size of the problem. Hence, an efficient heuristic approach is in need to solve large scale problems appearing in many practical applications including transportation, production-inventory management, supply chain, facility expansion and location decision, and logistics. In this paper, we present a new approach for solving the general NPLNFP in a continuous formulation by adapting a dynamic domain contraction. A Dynamic Domain Contraction (DDC) algorithm is presented and preliminary computational results on a wide range of test problems are reported. The results show that the proposed algorithm generates solutions within 0 to 0.94 % of optimality in all instances that the exact solutions are available from a branch and bound method.     

Telecommunication Link Restoration Planning with Multiple Facility Types

To ensure uninterrupted service, telecommunication networks contain excess (spare) capacity for rerouting (restoring) traffic in the event of a link failure. We study the NP-hard capacity planning problem of economically installing spare capacity on a network to permit link restoration of steady-state traffic. We present a planning model that incorporates multiple facility types, and develop optimization-based heuristic solution methods based on solving a linear programming relaxation and minimum cost network flow subproblems. We establish bounds on the performance of the algorithms, and discuss problem instances that nearly achieve these worst-case bounds. In tests on three real-world problems and numerous randomly-generated problems containing up to 50 nodes and 150 edges, the heuristics provide good solutions (often within 0.5% of optimality) to problems with single facility type, in equivalent or less time than methods from the literature. For multi-facility problems, the gap between our heuristic solution values and the linear programming bounds are larger. However, for small graphs, we show that the optimal linear programming value does not provide a tight bound on the optimal integer value, and our heuristic solutions are closer to optimality than implied by the gaps.     

Minimizing the sum of job completion times on capacitated two-parallel machines

This paper considers a scheduling problem with two identical parallel machines. One has unlimited capacity; the other can only run for a fixed time. A given set of jobs must be scheduled on the two machines with the goal of minimizing the sum of their completion times. The paper proposes an optimal branch and bound algorithm which employs three powerful elements, including an algorithm for computing the upper bound, a lower bound algorithm, and a fathoming condition. The branch and bound algorithm was tested on problems of various sizes and parameters. The results show that the algorithm is quite efficient to solve all the test problems. In particular, the total computation time for the hardest problem is less than 0.1 second for a set of 100 problem instances. An important finding of the tests is that the upper bound algorithm can actually find optimal solutions to a quite large number of problems.     

分支定界算法求解带有释放时间的单机双代理调度问题

本文研究了带有释放时间的单机双代理调度问题,目标函数为极小化最大完工时间和。为了便于利用优化软件求解,建立了混合整数规划模型。考虑到该问题具有NP困难性,因此采用近似与精确算法分别求解不同规模问题。针对大规模问题,提出了优势代理优先启发式算法,并证明了其渐近最优性。针对小规模问题,设计了分支定界法进行最优求解,其中基于释放时间的分支规则和基于加工中断的下界有效地减少了运算时间。最后,通过数值测试验证了分支定界算法的有效性以及启发式算法的收敛性。     

一类多商品设施选址问题的基于线性松弛解的启发式方法

多商品设施选址问题是众多设施选址问题中一类重要而困难的问题.在这一问题中,顾客的需求可能包含不止一种商品.对于大规模问题,成熟的商业求解器往往不能在满意的时间内找到高质量的可行解.研究了无容量限制的单货源多商品设施选址问题的一般形式,并给出了应用于此类问题的两个启发式方法.这两个方法基于原选址问题的线性规划松弛问题的最优解,分别通过求解紧问题和邻域搜索的方式给出了原问题的一个可行上界.理论分析指出所提方法可以实施于任意可行问题的实例.数值结果表明所提方法可以显著地提高求解器求解此类设施选址问题的求解效率.     

An Improved Branch & Bound Method for the Uncapacitated Competitive Location Problem

In this paper, the problem of locating new facilities in a competitive environment is considered. The problem is formulated as the firm expected profit maximization and a set of nodes is selected in a graph representing the geographical zone. Profit depends on fixed and deterministic location costs and, since customers are independent decision-makers, on the expected market share. The problem is an instance of nonlinear integer programming, because the objective function is concave and submodular. Due to this complexity a branch & bound method is developed for solving small size problems (that is, when the number of nodes is less than 50), while a heuristic is necessary for larger problems. The branch & bound is called data-correcting method, while the approximate solutions are obtained using the heuristic-concentration method.     

A fast heuristic algorithm for the maximum concurrent <Emphasis Type="Italic">k</Emphasis>-splittable flow problem

In this paper, we propose a fast heuristic algorithm for the maximum concurrent k-splittable flow problem. In such an optimization problem, one is concerned with maximizing the routable demand fraction across a capacitated network, given a set of commodities and a constant k expressing the number of paths that can be used at most to route flows for each commodity. Starting from known results on the k-splittable flow problem, we design an algorithm based on a multistart randomized scheme which exploits an adapted extension of the augmenting path algorithm to produce starting solutions for our problem, which are then enhanced by means of an iterative improvement routine. The proposed algorithm has been tested on several sets of instances, and the results of an extensive experimental analysis are provided in association with a comparison to the results obtained by a different heuristic approach and an exact algorithm based on branch and bound rules.     

同时加工排序问题的分支定界法和启发式算法

同时加工机器或者称为批加工机器是可以同时加工多个工件的机器．本文研究使带权总完工时间为最小的同时加工排序问题1|B|∑wjGj.这个问题的计算复杂性还没有解决．我们给出这个问题的精确解法——分支定界法和几个启发式算法，并且用较多实例对启发式算法的性能进行了比较．     

A lower bound for weighted completion time variance

We consider a single machine scheduling problem to minimize the weighted completion time variance. This problem is known to be NP-hard. We propose a heuristic and a lower bound based on job splitting and the Viswanathkumar and Srinivasan procedure. The test on more than 2000 instances shows that this lower bound is very tight and the heuristic yields solutions very close to optimal ones since the gap between the solution given by the heuristic and the lower bound is very small.     

Speeding up branch and bound algorithms for solving the maximum clique problem

In this paper we consider two branch and bound algorithms for the maximum clique problem which demonstrate the best performance on DIMACS instances among the existing methods. These algorithms are MCS algorithm by Tomita et al. (2010) and MAXSAT algorithm by Li and Quan (2010a, b). We suggest a general approach which allows us to speed up considerably these branch and bound algorithms on hard instances. The idea is to apply a powerful heuristic for obtaining an initial solution of high quality. This solution is then used to prune branches in the main branch and bound algorithm. For this purpose we apply ILS heuristic by Andrade et al. (J Heuristics 18(4):525–547, 2012). The best results are obtained for p_hat1000-3 instance and gen instances with up to 11,000 times speedup.