A parallel algorithm for the 0–1 knapsack problem

Research efforts on parallel exact algorithms for the 0–1 knapsack problem have up to now concentrated on solving small problems (at most 1,000 objects) and in many cases results have only been obtained by simulation of the parallel algorithm. After a brief review of a well known sequential branch-and-bound algorithm we discuss a new parallel algorithm for the 0–1 knapsack problem which exploits the potential parallelism that exists during the backtracking steps of the branch-and-bound algorithm. We report results for our parallel algorithm on a transputer network for problems with up to 20,000 objects. The speedup obtained is nearly linear for 2, 4, and 8 processors except when there is a strong correlation between the profit and weight of the objects.     

The general problem solving algorithm and its implementation

By generalising problem solving techniques such as divide-and-conquer, dynamic programming, tree and graph searching, integer programming and branch-and-bound, a general problem solving algorithm is deduced. Various examples of the use of this algorithm are given and its implementation on both sequential and parallel machines, such as the cosmic cube, is discussed.     

Evaluation of a parallel branch-and-bound algorithm on a class ofmultiprocessors

We propose and evaluate a parallel “decomposite best-first” search branch-and-bound algorithm (dbs) for MIN-based multiprocessor systems. We start with a new probabilistic model to estimate the number of evaluated nodes for a serial best-first search branch-and-bound algorithm. This analysis is used in predicting the parallel algorithm speed-up. The proposed algorithm initially decomposes a problem into N subproblems, where N is the number of processors available in a multiprocessor. Afterwards, each processor executes the serial best-first search to find a local feasible solution. Local solutions are broadcasted through the network to compute the final solution. A conflict-free mapping scheme, known as the step-by-step spread, is used for subproblem distribution on the MIN. A speedup expression for the parallel algorithm is then derived using the serial best-first search node evaluation model. Our analysis considers both computation and communication overheads for providing realistic speed-up. Communication modeling is also extended for the parallel global best-first search technique. All the analytical results are validated via simulation. For large systems, when communication overhead is taken into consideration, it is observed that the parallel decomposite best-first search algorithm provides better speed-up compared to other reported schemes     

On a lower bound on the computational complexity of a parallel implementation of the branch-and-bound method

We study parallel complexity of the branch-and-bound method for optimization problems. We consider a standard implementation scheme for the branch-and-bound method on a parallel system, in which first only one processor is working, and then the resulting subtasks are given out to other processors. For this scheme, we give a lower bound on the parallel complexity independent of the problem. We study the complexity of this scheme for the Boolean knapsack problem. For a classical algorithmically hard example, we obtain parallel complexity bounds and show that these bounds coincide in order with each other and with the common lower bound on parallel complexity. Thus, we show that the common lower bound is achieved, in the order, for some optimization problems.     

Single machine weighted earliness–tardiness penalty problem with a common due date

In this paper, we have considered a class of single machine job scheduling problems where the objective is to minimize the weighted sum of earliness–tardiness penalties of jobs. The weights are job-independent but they depend on whether a job is early or tardy. The restricted version of the problem where the common due date is smaller than a critical value, is known to be NP-complete. While dynamic programming formulation runs out of memory for large problem instances, depth-first branch-and-bound formulation runs slow for large problems since it uses a tree search space. In this paper, we have suggested an algorithm to optimally solve large instances of the restricted version of the problem. The algorithm uses a graph search space. Unlike dynamic programming, the algorithm can output optimal solutions even when available memory is limited. It has been found to run faster than dynamic programming and depth-first branch-and-bound formulations and can solve much larger instances of the problem in reasonable time. New upper and lower bounds have been proposed and used. Experimental findings are given in detail.Scope and purposeA class of single machine problems arising out of scheduling jobs in JIT environment has been considered in this paper. The objective is to minimize the total weighted earliness–tardiness penalties of jobs. In this paper, we have presented a new algorithm and conducted extensive empirical runs to show that the new algorithm performs much better than the existing approaches in solving large instances of the problem.     

Scheduling two-machine no-wait open shops to minimize makespan

This paper examines the problem of scheduling two-machine no-wait open shops to minimize makespan. The problem is known to be strongly NP-hard. An exact algorithm, based on a branch-and-bound scheme, is developed to optimally solve medium-size problems. A number of dominance rules are proposed to improve the search efficiency of the branch-and-bound algorithm. An efficient two-phase heuristic algorithm is presented for solving large-size problems. Computational results show that the branch-and-bound algorithm can solve problems with up to 100 jobs within a reasonable amount of time. For large-size problems, the solution obtained by the heuristic algorithm has an average percentage deviation of 0.24% from a lower bound value.     

Logic based Benders' decomposition for orthogonal stock cutting problems

We consider the problem of packing a set of rectangular items into a strip of fixed width, without overlapping, using minimum height. Items must be packed with their edges parallel to those of the strip, but rotation by 90° is allowed. The problem is usually solved through branch-and-bound algorithms. We propose an alternative method, based on Benders' decomposition. The master problem is solved through a new ILP model based on the arc flow formulation, while constraint programming is used to solve the slave problem. The resulting method is hybridized with a state-of-the-art branch-and-bound algorithm. Computational experiments on classical benchmarks from the literature show the effectiveness of the proposed approach. We additionally show that the algorithm can be successfully used to solve relevant related problems, like rectangle packing and pallet loading.     

Minimizing the weighted sum of squared tardiness on a single machine

This paper considers a problem in which there is a set of jobs to be sequenced on a single machine. Each job has a weight and the objective is to sequence the jobs to minimize total weighted squared tardiness. A branch-and-bound algorithm is developed for optimally solving the problem. Several dominance conditions are presented for possible inclusion in the branch-and-bound algorithm. The dominance conditions are included in the branch-and-bound algorithm, which is tested on randomly generated problems of various numbers of jobs, due date tightness and due date ranges. The results show that the dominance conditions dramatically improve the efficiency of the branch-and-bound algorithm.     

一类电路布线问题的分支限界算法

分支限界策略对很多实际问题是重要和有效的。论文首先提出了一类电路布线问题,然后给出了解决该问题的分支限界算法并分析了所给出算法的复杂度。实验结果验证了所提出方法的有效性。     

基于有效并行求解策略的显式有限元分析并行算法

针对大规模结构非线性动力问题的有限元分析非常耗时,基于消息传递接口（MPI）机群环境,提出多种基于并行求解策略的显式有限元并行算法。基于显式消息传递的区域分解技术,采取重叠、非重叠区域分解技术及动态任务分配方法,通过将计算与通信重叠,优化处理器间的通信,对非重叠通信区域分解并行算法、重叠通信区域分解并行算法、群动态任务分配算法、动态任务分配算法及动态负载平衡算法进行研究。为在机群环境下实现非线性动力有限元分析,开发了基于有效并行求解策略的显式有限元并行算法。编写了基于消息传递编程模式的并行有限元程序,在工作站机群上实现了数值算例,分析了算法的性能,并与传统的Newmark算法进行了比较。算例表明：群动态任务分配算法的性能优于动态任务分配算法,低于区域分解算法的性能,动态负载平衡算法最优。对相同规模的问题提出的算法比Newmark算法快,优于Newmark算法。对结构非线性动力问题的有限元分析,所提出的并行算法是可行有效的。     

Dual constrained single machine sequencing to minimize total weighted completion time

We study a single-machine sequencing problem with both release dates and deadlines to minimize the total weighted completion time. We propose a branch-and-bound algorithm for this problem. The algorithm exploits an effective lower bound and a dynamic programming dominance technique. As a byproduct of the lower bound, we have developed a new algorithm for the generalized isotonic regression problem; the algorithm can also be used as an O(nlogn)-time timetabling routine in earliness-tardiness scheduling. Extensive computational experiments indicate that the proposed branch-and-bound algorithm competes favorably with a dynamic programming procedure. Note to Practitioners-Real-life production systems usually involve multiple machines and resources. The configurations of such systems may be complex and subject to change over time. Therefore, model-based solution approaches, which aim to solve scheduling problems for specific configurations, will inevitably run into difficulties. By contrast, decomposition methods are much more expressive and extensible. The single-machine problem and its solution procedure studied in this paper will prove useful to a decomposition method that decomposes multiple-machine, multiple-resource scheduling problems into a number of single-machine problems. The total weighted completion time objective is relevant to production environments where inventory levels and manufacturing cycle times are key concerns. Future research can be pursued along two directions. First, it seems to be necessary to further generalize the problem to consider also negative job weights. Second, the solution procedure developed here is ready to be incorporated into a machine-oriented decomposition method such as the shifting bottleneck procedure.     

An efficient coarse-grain multicomputer algorithm for the minimum cost parenthesizing problem

Several problems modeled by dynamic programming have been solved using a coarse-grain multicomputer parallel model (CGM for short). These problems use either polyadic dynamic programming or monadic non-serial dynamic programming. In this paper, we address the general case: we propose a parallel algorithm in the CGM model with p processors for the Optimal String Parenthesizing Problem or Minimum Cost Parenthesizing Problem, which is a typical polyadic non-serial dynamic programming problem. The algorithm we obtain requires ?(2p)^1/2? communication rounds and, at most, O(n ³/p) time-steps on p processors. This new CGM algorithm performs better than the previously most efficient solution, which uses p communication rounds.     

Note on minimizing total tardiness in a two-machine flowshop

This note considers the problem of sequencing jobs to minimize total tardiness in a two-machine flowshop. The note shows how three dominance conditions and a lower bound previously developed for this problem can be improved. The note also proposes a new dominance condition. A branch-and-bound algorithm is developed that uses the improvements and new dominance condition. The algorithm is tested on randomly generated problems and the results of the test show that the improvements and new dominance condition improves the branch-and-bound algorithm's efficiency.     

A randomized parallel branch-and-bound algorithm

Randomized algorithms are algorithms that employ randomness in their solution method. We show that the performance of randomized algorithms is less affected by factors that prevent most parallel deterministic algorithms from attaining their theoretical speedup bounds. A major reason is that the mapping of randomized algorithms onto multiprocessors involves very little scheduling or communication overhead. Furthermore, reliability is enhanced because the failure of a single processor leads only to degradation, not failure, of the algorithm. We present results of an extensive simulation done on a multiprocessor simulator, running a randomized branch-and-bound algorithm. The particular case we consider is the knapsack problem, due to its ease of formulation. We observe the largest speedups in precisely those problems that take large amounts of time to solve. This work has been supported by the U.S. Army Research Office under Contract No. DAAG 29-85-K-0236.     

The total completion time open shop scheduling problem with a given sequence of jobs on one machine

This paper addresses the open shop scheduling problem to minimize the total completion time, provided that one of the machines has to process the jobs in a given sequence. The problem is NP-hard in the strong sense even for the two-machine case. A lower bound is derived based on the optimal solution of a relaxed problem in which the operations on every machine may overlap except for the machine with a given sequence of jobs. This relaxed problem is NP-hard in the ordinary sense, however it can be quickly solved via a decomposition into subset-sum problems. Both heuristic and branch-and-bound algorithm are proposed. Experimental results show that the heuristic is efficient for solving large-scaled problems, and the branch-and-bound algorithm performs well on small-scaled problems.Scope and purposeShop scheduling problems, widely used in the modeling of industrial production processes, are receiving an increasing amount of attention from researchers. To model practical production processes more closely, additional processing restrictions can be introduced, e.g., the resource constraints, the no-wait in process requirement, the precedence constraints, etc. This paper considers the total completion time open shop scheduling problem with a given sequence of jobs on one machine. This model belongs to a new class of shop scheduling problems under machine-dependent precedence constraints. This problem is NP-hard in the strong sense. A heuristic is proposed to efficiently solve large-scaled problems and a branch-and-bound algorithm is presented to optimally solve small-scaled problems. Computational experience is also reported.     

An application of parallel virtual machine framework to film production problem

Along with the rapid progress in computer technologies, both the theoretical foundations and practical applications of operations research are becoming more and more profound. In the literature, many techniques have been thus proposed to deal with real-world problems. However, the problems often exhibit complicated structures, and it is difficult to derive exact solutions in a reasonable time. PVM (Parallel Virtual Machine), the platform of our study, is a widely used environment in the world of parallel computing. It can be used to integrate existing department facilities without incurring additional hardware costs. Furthermore, the ease in programming also facilitates a wide adoption of PVM. In our study, we incorporate the concepts of the branch-and-bound method, multiprocess programming, and shared memory to design a parallel branch-and-bound algorithm to cope with the problem of minimizing talent hold cost in film production. We conduct a series of computational experiments to measure the effectiveness of our paralleization scheme. The results reveal that the speedup based upon our parallel algorithm is significant. This research provides a convincing demonstration in achieving effective parallelization with low costs.     

A neural network approach for a robot task sequencing problem

This paper presents a neural network approach with successful implementation for the robot task-sequencing problem. The problem addresses the sequencing of tasks comprising loading and unloading of parts into and from the machines by a material-handling robot. The performance criterion is to minimize a weighted objective of the total robot travel time for a set of tasks and the tardiness of the tasks being sequenced. A three-phased parallel implementation of the neural network algorithm on Thinking Machine's CM-5 parallel computer is also presented which resulted in a dramatic increase in the speed of finding solutions. To evaluate the performance of the neural network approach, a branch-and-bound method and a heuristic procedure have been developed for the problem. The neural network method is shown to give good results and is especially useful for solving large problems on a parallel-computing platform.     

A new optimal algorithm for the permutation flow-shop problem and its parallel implementation

This paper describes a new parallel algorithm for solving n-job, m-machine flow-shop problems. The algorithm is basically a parallelization of the usual branch-and-bound method. It also takes advantage of all search method to keep high efficiency of parallel processing, when the sub-problem becomes smaller than certain size. It is shown that its implementation on both nCUBE2 and LUNA88k2 gives very good performance characteristics.     

供应链环境下需求不确定的批量生产计划

针对由单个制造商、单一产品和多个客户构成的供应链系统,建立了分散控制下系统利润最大化模型,提出了新的客户选择可变方案,分别设计了遗传算法和分枝定界法对问题进行了求解。通过实例仿真与前人提出的客户选择不可变方案进行了比较分析,结果证明,分枝定界法更适合求解规模较小的问题,而遗传算法可以通过调整种群规模和遗传算子来解决规模较大的问题;与客户选择不可变相比,当客户选择可变时,系统能获取较大的期望利润。