In this study, we theoretically compare integer programming models for the two-dimensional two-staged knapsack problem. Including the well-known level packing model, we introduce two pattern-based models called the st...
详细信息
In this study, we theoretically compare integer programming models for the two-dimensional two-staged knapsack problem. Including the well-known level packing model, we introduce two pattern-based models called the strip packing model and the staged pattern model derived from integer programming models for the two-dimensional two-staged cutting stock problem. We show that the level packing model provides weaker linear programming (LP) relaxation bounds than pattern-based models. Furthermore, we also present upper bounds on the LP-relaxation bound of the level packing model, which can be obtained from the LP-relaxation bounds of the pattern-based models.
With the rapid development of e-commerce, the orders processed in B2C warehouses are characterised by heterogeneous and small volume. The traditional storage assignment strategies used in the picker-to-parts warehouse...
详细信息
With the rapid development of e-commerce, the orders processed in B2C warehouses are characterised by heterogeneous and small volume. The traditional storage assignment strategies used in the picker-to-parts warehouses do not have advantage any more. In this case, the scattered storage strategy is a good alternative. In this paper, we study a new scattered storage strategy that allows the same product to be placed in multiple storage locations. The correlation between products which reflects how frequently any two products will be ordered together in the same order is considered. The problem is formulated as a 0-1 integerprogramming model to minimise the weighted sum of distances between the products, with weight being the elements of the correlation matrix. To solve large-scale problems, a GA and a basic PSO algorithm are developed. To improve solution quality, a new PSO algorithm based on the problem characteristic is designed and a hybrid algorithm combing it with GA is proposed. Experiments show that the solutions of these algorithms are close to the optimal solutions for the small-sale problems. For larger problems, the specially designed new PSO greatly improves solution quality as compared to the basic algorithms and the hybrid algorithm makes further improvement.
The scope of the assembly line balancing problem in research is clear, with well-defined sets of assumptions, parameters, and objective functions. In application, these borders are frequently transgressed. Many of the...
详细信息
The scope of the assembly line balancing problem in research is clear, with well-defined sets of assumptions, parameters, and objective functions. In application, these borders are frequently transgressed. Many of these deviations are internal to the assembly line balancing problem itself, arising from any of the physical or technological features in modem assembly lines. Other issues are founded in the tight coupling of assembly line balancing with external production planning and management problems, as assembly lines are at the intersection of multiple related problems in job sequencing, part flow logistics, worker safety, and quality. General assembly line balancing is devoted to studying the solution techniques necessary to model these applied line balancing problems. This article presents a complex line balancing problem based on the real production environment of our industrial partner, featuring several extensions for task-to-task relationships, station characteristics limiting assignment, and parallel worker zoning interactions. A heuristic, combining rank-position-weighting, last-fit improvement and iterative blocking scheme, and an integer program that can manage multiple constraint types simultaneously, are developed. An experiment is conducted testing each of these new solution methods upon a battery of testbed problems, measuring solution quality, runtime, and achievement of feasibility. Results indicate that the integerprogramming model provides a viable solution method for those industries with access to commercial solvers.
The angular-metric travelling salesman problem (AngleTSP) asks for a Hamiltonian cycle for given points in the Euclidean plane mimimizing the sum of all turning angles. Setting as objective the linear combination of t...
详细信息
The angular-metric travelling salesman problem (AngleTSP) asks for a Hamiltonian cycle for given points in the Euclidean plane mimimizing the sum of all turning angles. Setting as objective the linear combination of these angles with the distances of the classical TSP, gives rise to the angular-distance-metric travelling salesman problem (AngleDistanceTSP). Since both problems are NP-hard, we first introduce a wide range of heuristic approaches, motivated by the typical geometric structure of optimal solutions. In particular, we exploit lens-shaped neighbourhoods of edges and a decomposition of the graph into layers of convex hulls, which are then merged into a tour. Secondly, we consider an ILP model based on the more general quadratic travelling salesman problem (QTSP). By rounding its fractional solutions we obtain a collection of subtours, paths and isolated points, which are then combined into a tour by various strategies, all of them involving auxiliary ILP models. Finally, different improvement heuristics are proposed, most notably a matheuristic which locally reoptimizes the solution for rectangular sectors of the given point set by an ILP approach. Results of extensive computational experiments using benchmark instances from the literature illustrate the Pareto-efficient frontier of algorithms in a (running time, objective value)-space. It turns out that our new methods clearly dominate previously published heuristics. (C) 2019 Elsevier Ltd. All rights reserved.
Turret-based CNC machines can change from one tool to another by simply rotating the turret. However, each tool must be positioned at the exact same place on the turret for each batch of the same product. In industria...
详细信息
This paper considers a single product disassembly lot sizing problem with disposal decision (DLSPD) in order to reduce the costs as well as environmental impacts related to returned products. This is the problem of de...
详细信息
In this paper, we address the constrained two-dimensional rectangular guillotine single large placement problem (2D_R_CG_SLOPP). This problem involves cutting a rectangular object to produce smaller rectangular items ...
详细信息
In this paper, we address the constrained two-dimensional rectangular guillotine single large placement problem (2D_R_CG_SLOPP). This problem involves cutting a rectangular object to produce smaller rectangular items from orthogonal guillotine cuts. In addition, there is an upper limit on the number of copies that can be produced of each item type. To model this problem, we propose a new pseudopolynomial integer nonlinear programming (INLP) formulation and obtain an equivalent integer linear programming (ILP) formulation from it. Additionally, we developed a procedure to reduce the numbers of variables and constraints of the integer linear programming (ILP) formulation, without loss of optimality. From the ILP formulation, we derive two new pseudopolynomial models for particular cases of the 2D_R_CG_SLOPP, which consider only two-staged or one-group patterns. Finally, as a specific solution method for the 2D_R_CG_SLOPP, we apply Benders decomposition to the proposed ILP formulation and develop a branch-and-Benders-cut algorithm. All proposed approaches are evaluated through computational experiments using benchmark instances and compared with other formulations available in the literature. The results show that the new formulations are appropriate in scenarios characterized by few item types that are large with respect to the object's dimensions.
In this work a balanced k-way partitioning problem with weight constraints is defined to model the sports team realignment. Sports teams must be partitioned into a fixed number of groups according to some regulations,...
详细信息
In this work a balanced k-way partitioning problem with weight constraints is defined to model the sports team realignment. Sports teams must be partitioned into a fixed number of groups according to some regulations, where the total distance of the road trips that all teams must travel to play a double round robin tournament in each group is minimized. Two integerprogramming formulations for this problem are introduced, and the validity of three families of inequalities associated to the polytope of these formulations is proved. The performance of a tabu search procedure and a branch and cut algorithm, which uses the valid inequalities as cuts, is evaluated over simulated and real-world instances. In particular, an optimal solution for the realignment of the Ecuadorian football league is reported and the methodology can be suitable adapted for the realignment of other sports leagues.
In the second category of the Ecuadorian football league, a set of football teams must be grouped into k geographical zones according to some regulations, where the total distance of the road trips that all teams must...
详细信息
ISBN:
(纸本)9783319455877;9783319455860
In the second category of the Ecuadorian football league, a set of football teams must be grouped into k geographical zones according to some regulations, where the total distance of the road trips that all teams must travel to play a Double Round Robin Tournament in each zone is minimized. This problem can be modeled as a k-clique partitioning problem with constraints on the sizes and weights of the cliques. An integerprogramming formulation and a heuristic approach were developed to provide a solution to the problem which has been implemented in the 2015 edition of the aforementioned football championship.
In order to solve the key issues of urban rail train routing problem, which were considered as to determine running section and turn-back stations, combined with practice experience, a multi-objective 0-1 mixed intege...
详细信息
暂无评论