下料问题的优化模型及其快速算法

结合生产实际中具体的下料问题,本文建立了该类问题的优化模型,并提出下料方式的遴选三准则,即高利用率优先准则,长度优先准则和时间优先准则.运用本文的算法对一维下料的利用率高达99.6%,机器时间4秒.对二维的利用率为98.9%,机器时间约7秒.     

Economic lot sizes and vehicle scheduling

In this paper a relationship between the vehicle scheduling problem and the dynamic lot size problem is considered. For the latter problem we assume that order quantities for different products can be determined separately. Demand is known over our n-period production planning horizon. For a certain product our task is to decide for each period if it should be produced or not. If it is produced, what is its economic lot size? Our aim here is to minimize the combined set-up and inventory holding costs. The optimal solution of this problem is given by the well-known Wagner-Whitin dynamic lot size algorithm. Also many heuristics for solving this problem have been presented. In this article we point out the analogy of the dynamic lot size problem to a certain vehicle scheduling problem. For solving vehicle scheduling problems the heuristic algorithm developed by Clark and Wright in very often used. Applying this algorithm to the equivalent vehicle scheduling problem we obtain by analogy a simple heuristic algorithm for the dynamic lot size problem. Numerical results indicate that computation time is reduced by about 50% compared to the Wagner-Whitin algorithm. The average cost appears to be approximately 0.8% higher than optimum.     

Parallel bundle-based decomposition for large-scale structured mathematical programming problems

In this paper, we present parallel bundle-based decomposition algorithms to solve a class of structured large-scale convex optimization problems. An example in this class of problems is the block-angular linear programming problem. By dualizing, we transform the original problem to an unconstrained nonsmooth concave optimization problem which is in turn solved by using a modified bundle method. Further, this dual problem consists of a collection of smaller independent subproblems which give rise to the parallel algorithms. We discuss the implementation on the CRYSTAL multi-computer. Finally, we present computational experience with block-angular linear programming problems and observe that more than 70% efficiency can be obtained using up to eleven processors for one group of test problems, and more than 60% efficiency can be obtained for relatively smaller problems using up to five processors for another group of problems.     

Stochastic nuclear outages semidefinite relaxations

This paper deals with stochastic scheduling of nuclear power plant outages. Focusing on the main constraints of the problem, we propose a stochastic formulation with a discrete distribution for random variables, that leads to a mixed 0/1 quadratically constrained quadratic program. Then we investigate semidefinite relaxations for solving this hard problem. Numerical results on several instances of the problem show the efficiency of this approach, i.e., the gap between the optimal solution and the continuous relaxation is on average equal to 53.35 % whereas the semidefinite relaxation yields an average gap of 2.76 %. A feasible solution is then obtained with a randomized rounding procedure.     

The EOQ problem with decidable warehouse capacity: Analysis, solution approaches and applications

The Economic Order Quantity (EOQ) problem is a fundamental problem in supply and inventory management. In its classical setting, solutions are not affected by the warehouse capacity. We study a type of EOQ problem where the (maximum) warehouse capacity is a decision variable. Furthermore, we assume that the warehouse cost dominates all the other inventory holding costs. We call this the EOQ-Max problem and the D-EOQ-Max problem, if the product is continuously divisible and discrete, respectively. The EOQ-Max problem admits a closed form optimal solution, while the D-EOQ-Max problem does not because its objective function may have several local minima. We present an optimal polynomial time algorithm for the discrete problem. Construction of this algorithm is supported by the fact that continuous relaxation of the D-EOQ-Max problem provides a solution that can be up to 50% worse than the optimal solution, and this worst-case error bound is tight. Applications of the D-EOQ-Max problem include supply and inventory management, logistics and scheduling.     

Survivable network design with shared-protection routing

In this paper we study the problem of designing a survivable telecommunication network with shared-protection routing. We develop a heuristic algorithm to solve this problem. Recent results in the area of global re-routing have been used to obtain very tight lower bounds for the problem. Our results indicate that in a majority of problem instances, the average gap between the heuristic solutions and the lower bounds is within 5%. Computational experience is reported on randomly generated problem instances with up to 35 nodes, 80 edges and 595 demand pairs and also on the instances available in SNDlib database.     

The use of genetic algorithms to solve the economic lot size scheduling problem

The purpose of this paper is to investigate the use genetic algorithms (GAs) for solving the Economic Lot Size Scheduling Problem (ELSP). The ELSP is formulated using the Basic Period (BP) approach which results in a problem having one continuous decision variable and a number of integer decision variables equal to the number of products being produced. This formulation is ideally suited for using GAs. The GA is tested on Bomberger's classical problem. The resulting solutions were better than those obtained using an iterative dynamic programming (DP) approach. The total cost of GA solutions to the problem with utilization up to 65% were within 3.4% of the lower bound. The GA also performed well for higher utilization yielding solutions within 13.87% of the lower bound for utilization up to 86%. The GA was tested on a 30-item problem and good solutions were obtained. The results of the GA under different binary representations, crossover methods, and initialization methods are compared to identify the best settings. The results indicate that for this particular problem, binary representation works better than Gray coding, 2-point crossover is best, and an infeasible starting population is better than feasible.     

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 exact algorithm for the sequential ordering problem and its application to switching energy minimization in compilers

This article presents an exact algorithm for the precedence-constrained traveling salesman problem, which is also known as the sequential ordering problem. This NP-hard problem has applications in various domains, including operational research and compilers. In this article, the problem is presented and solved in the context of minimizing switching energy in compilers. Most previous work on minimizing switching energy in the compiler domain has been limited to simple heuristics that are not guaranteed to give an optimal solution. In this work, we present an exact algorithm for solving the switching energy minimization problem using a branch-and-bound approach. The proposed algorithm is simple and intuitive, yet powerful. It is the first exact algorithm for the switching energy problem that is shown to solve real instances of the problem within a few seconds per instance. Compared to previous work in the operational research domain, the proposed algorithm is believed to be the most powerful exact algorithm that does not require a linear programming formulation. The proposed algorithm is experimentally evaluated using instances taken from a production compiler. The results show that with a time limit of 10 ms per node, the proposed algorithm optimally solves 99.8 % of the instances. It optimally solves instances with up to 598 nodes within a few seconds. The resulting switching cost is 16 % less than that produced without energy awareness and 5 % less than that produced by a commonly used heuristic.     

Warehouse location with production,inventory, and distribution decisions: a case study in the lube oil industry

In this paper, a supply chain management problem from a real case study is modeled and solved. A company in Pakistan wanted to outsource part of its warehousing activity to a third party logistics (3PL) provider. Consequently, the company had to decide on where to rent space in the 3PL warehouses. Knowing that such a strategic decision is affected by tactical and operational decisions, the problem is presented as a facility location problem integrating production, inventory, and distribution decisions. The problem is formulated as a mixed integer linear programming model which minimizes the total cost composed of location, distribution, production, and inventory costs. Several constraints specific to the situation and policy of the company were considered. A thorough analysis was done on the results obtained with respect to formulation efficiency, sensitivity analysis, and distribution of costs. In addition to the solution of the company problem, a set of 1215 problem instances was generated by varying five types of relevant costs in a full factorial manner. The solution of the generated problems always suggests to open in the same two locations and the integrality gaps averaged 0.062 % with a maximum of 0.102 %. On average, the major components of the total cost are production cost (96.6 %), transportation costs (2.7 %), and inventory holding costs (0.38 %). The total warehouse opening cost accounted for less than 0.05 % of the total costs.     

The resource-constrained modulo scheduling problem: an experimental study

In this paper, we focus on the resource-constrained modulo scheduling problem (RCMSP), a general periodic scheduling problem, abstracted from the problem solved by compilers when optimizing inner loops at instruction level for VLIW parallel processors. Heuristic solving scheme have been proposed since many years to solve this problem, among which the decomposed software pipeling method. In this method, a cyclic scheduling problem ignoring resource constraints is first considered and a so-called legal retiming of the operations is issued. Second, a standard acyclic problem, taking this retiming as input, is solved through list scheduling techniques. In this paper, we propose a novel hybrid approach, which uses the decomposed software pipeling method to obtain a good retiming. Then the obtained retiming is used to build an integer linear programming formulation of reduced size, which allows to solve it exactly. Experimental results show that a lot more problems are solved with this new approach. The gap to the optimal solution is less than 1 % on most of the tested problem instances and the method appears to be competitive with a recently proposed constraint programming algorithm (Bonfietti et al., Lect. Notes Comput. Sci. 6876:130–144, 2011).     

Routing and wavelength assignment by partition colouring

The problem of routing and wavelength assignment in all-optical networks may be solved by a combined approach involving the computation of alternative routes for the lightpaths, followed by the solution of a partition colouring problem in a conflict graph. A new tabu search heuristic is also proposed for the partition colouring problem, which may be viewed as an extension of the graph colouring problem. Computational experiments are reported, showing that the tabu search heuristic outperforms the best heuristic for partition colouring by approximately 20% in the average and illustrating that the new approach for the problem of routing and wavelength assignment is more robust than a well established heuristic for this problem.     

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%.     

A real delivery problem dealt with Monte Carlo Techniques

In this paper we use Monte Carlo Techniques to deal with a real world delivery problem of a food company in Valencia (Spain). The problem is modeled as a set of 11 instances of the well known Vehicle Routing Problem, VRP, with additional time constraints. Given that VRP is a NP-hard problem, a heuristic algorithm, based on Monte Carlo techniques, is implemented. The solution proposed by this heuristic algorithm reaches distance and money savings of about 20% and 5% respectively. This work has been partially supported by thePlan de Incentivo a la Investigación/98 of the Universidad Politécnica de Valencia, under the project “Técnicas Monte Carlo aplicadas a Problemas de Rutas de Vehículos”.     

Emergency response in natural disaster management: Allocation and scheduling of rescue units

Natural disasters, such as earthquakes, tsunamis and hurricanes, cause tremendous harm each year. In order to reduce casualties and economic losses during the response phase, rescue units must be allocated and scheduled efficiently. As this problem is one of the key issues in emergency response and has been addressed only rarely in literature, this paper develops a corresponding decision support model that minimizes the sum of completion times of incidents weighted by their severity. The presented problem is a generalization of the parallel-machine scheduling problem with unrelated machines, non-batch sequence-dependent setup times and a weighted sum of completion times – thus, it is NP-hard. Using literature on scheduling and routing, we propose and computationally compare several heuristics, including a Monte Carlo-based heuristic, the joint application of 8 construction heuristics and 5 improvement heuristics, and GRASP metaheuristics. Our results show that problem instances (with up to 40 incidents and 40 rescue units) can be solved in less than a second, with results being at most 10.9% up to 33.9% higher than optimal values. Compared to current best practice solutions, the overall harm can be reduced by up to 81.8%.     

Optimizing color picture tubes by high-cost nonlinear programming

In this paper we discuss the application of optimization techniques for the design of several parts of the color picture tube, the key component of television sets and computer monitors. These projects have been carried out for Philips Display Components in Eindhoven. Philips developed several computer simulation models of picture tube parts. Designers use these models to simulate the physical behavior of a particular part design. Depending on the amount of detail in the model, the running time of a typical simulation ranges from one up to 10 hours. Tube designers are confronted with the problem of finding settings for a large number of design parameters that are optimal with respect to several simulated tube characteristics. This problem can be modeled as a so-called high-cost nonlinear programming problem. This paper reports on the successful application of our four-step compact model approach to solve this problem. The presented results are based on four projects in which we optimized picture tube parts. Among the realized benefits for Philips are a design improvement of 30% and a time-to-market reduction of 50–60%.     

Solving school bus routing problems through integer programming

In this paper, an exact solution approach is described for solving a real-life school bus routing problem (SBRP) for transporting the students of an elementary school throughout central Ankara, Turkey. The problem is modelled as a capacitated and distance constrained open vehicle routing problem and an associated integer linear program is presented. The integer program borrows some well-known inequalities from the vehicle routing problem, which are also shown to be valid for the SBRP under consideration. The optimal solution of the problem is computed using the proposed formulation, resulting in a saving of up to 28.6% in total travelling cost as compared to the current implementation.     

An application of the branch,bound, and remember algorithm to a new simple assembly line balancing dataset

The simple assembly line balancing problem (SALBP) is a well-studied NP-complete problem for which a new problem database of generated instances was published in 2013. This paper describes the application of a branch, bound, and remember (BB&R) algorithm using the cyclic best-first search strategy to this new database to produce provably exact solutions for 86% of the unsolved problems in this database. A new backtracking rule to save memory is employed to allow the BB&R algorithm to solve many of the largest problems in the database.     

Continuum percolation with steps in the square or the disc

In 1961 Gilbert defined a model of continuum percolation in which points are placed in the plane according to a Poisson process of density 1, and two are joined if one lies within a disc of area A about the other. We prove some good bounds on the critical area A_c for percolation in this model. The proof is in two parts: First we give a rigorous reduction of the problem to a finite problem, and then we solve this problem using Monte‐Carlo methods. We prove that, with 99.99% confidence, the critical area lies between 4.508 and 4.515. For the corresponding problem with the disc replaced by the square we prove, again with 99.99% confidence, that the critical area lies between 4.392 and 4.398. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005     

A heuristic solution method for node routing based solid waste collection problems

This paper considers a real world waste collection problem in which glass, metal, plastics, or paper is brought to certain waste collection points by the citizens of a certain region. The collection of this waste from the collection points is therefore a node routing problem. The waste is delivered to special sites, so called intermediate facilities (IF), that are typically not identical with the vehicle depot. Since most waste collection points need not be visited every day, a planning period of several days has to be considered. In this context three related planning problems are considered. First, the periodic vehicle routing problem with intermediate facilities (PVRP-IF) is considered and an exact problem formulation is proposed. A set of benchmark instances is developed and an efficient hybrid solution method based on variable neighborhood search and dynamic programming is presented. Second, in a real world application the PVRP-IF is modified by permitting the return of partly loaded vehicles to the depots and by considering capacity limits at the IF. An average improvement of 25% in the routing cost is obtained compared to the current solution. Finally, a different but related problem, the so called multi-depot vehicle routing problem with inter-depot routes (MDVRPI) is considered. In this problem class just a single day is considered and the depots can act as an intermediate facility only at the end of a tour. For this problem several instances and benchmark solutions are available. It is shown that the algorithm outperforms all previously published metaheuristics for this problem class and finds the best solutions for all available benchmark instances.