In solving cutting stock problems, generally, cutting patterns are generated first, and then it is determined which cutting plans will be used. On the other hand, the difficulty of generating all cutting patterns and ...
详细信息
In solving cutting stock problems, generally, cutting patterns are generated first, and then it is determined which cutting plans will be used. On the other hand, the difficulty of generating all cutting patterns and often the large number of cutting patterns are the main problems encountered in this regard. In this study an integrated mathematical model that generates cutting patterns and finds the best patterns is developed for 1.5-dimensional cutting stock problems with order type and strip number constraints. This non-linear model has been linearized to eliminate solution difficulties. The performance of both models is compared with the performance of the model that uses the previously generated cutting patterns by using the randomly generated test problems. Obtained results show that the linear model, which also generates the cutting patterns itself, can be solved in a reasonable time up to a certain size. In particular, we believe that linearization of the nonlinear mathematical model for the problem will be an important contribution for the literature.
The relaxation complexity rc(X) of the set of integer points X contained in a polyhedron is the minimal number of inequalities needed to formulate a linear optimization problem over X without using auxiliary variables...
详细信息
The relaxation complexity rc(X) of the set of integer points X contained in a polyhedron is the minimal number of inequalities needed to formulate a linear optimization problem over X without using auxiliary variables. Besides its relevance in integerprogramming, this concept has interpretations in aspects of social choice, symmetric cryptanalysis, and machine learning. We employ efficient mixed-integerprogramming techniques to compute a robust and numerically more practical variant of the relaxation complexity. Our proposed models require row or column generation techniques and can be enhanced by symmetry handling and suitable propagation algorithms. Theoretically, we compare the quality of our models in terms of their LP relaxation values. The performance of those models is investigated on a broad test set and is underlined by their ability to solve challenging instances that could not be solved previously.
Multi-project staff scheduling optimization is a critical challenge in engineering management. However, traditional methods often overlook employee welfare, resulting in scheduling solutions that lack a people-centere...
详细信息
Multi-project staff scheduling optimization is a critical challenge in engineering management. However, traditional methods often overlook employee welfare, resulting in scheduling solutions that lack a people-centered approach. This study develops a multi-objective model that incorporates employee welfare to balance project performance and staff well-being. A mixed-integerprogramming model is proposed, integrating task allocation, resource scheduling, income growth, and workload balance as core optimization objectives. An improved Spider Wasp Optimization Algorithm (SWOIM) is employed to solve this model. The experimental results demonstrate that SWOIM outperforms conventional optimization algorithms in convergence speed, stability, and solution quality. It enhances staff scheduling efficiency while ensuring fair compensation and balanced workload distribution. A case study further validates the practical applicability of the proposed approach, showing that the optimized schedule not only improves task allocation but also enhances employee satisfaction and overall organizational performance. This study presents a people-centered scheduling framework aligned with sustainable workforce management principles and offers practical insights for improving multi-project coordination.
This paper treats a replenishment problem where an order in a single period is to be determined. Demand is assumed to be known for multiple periods. The first periods' demands are required to be satisfied by the o...
详细信息
This paper treats a replenishment problem where an order in a single period is to be determined. Demand is assumed to be known for multiple periods. The first periods' demands are required to be satisfied by the order, satisfying remaining demand is optional. Furthermore, a threshold needs to be satisfied, e.g., a minimum total order volume is given and orders can be placed only if they reach (or exceed) this volume. As a consequence, articles cannot be treated independently and, thus, we have to determine order volumes for all articles integratedly. The replenishment problem with multiple articles and an order threshold is formalized and its computational complexity is determined. We develop mixed-integer programming models and suited optimization approaches and apply them in static and dynamic problem settings. We see that the deterministic problem setting can be solved in reasonable time and that a decision maker can benefit from employing it in a decision support tool in a dynamic environment with uncertainty.
Given an undirected graph G = (V, E), a vertex k-cut of G is a vertex subset of V the removing of which disconnects the graph in at least k components. Given a graph G and an integer k >= 2, the vertex k-cut proble...
详细信息
Given an undirected graph G = (V, E), a vertex k-cut of G is a vertex subset of V the removing of which disconnects the graph in at least k components. Given a graph G and an integer k >= 2, the vertex k-cut problem consists in finding a vertex k-cut of G of minimum cardinality. We first prove that the problem is NP-hard for any fixed k >= 3. We then present a compact formulation, and an extended formulation from which we derive a column generation and a branching scheme. Extensive computational results prove the effectiveness of the proposed methods. (C) 2018 Elsevier B.V. All rights reserved.
Recently, Bianco and Caramia (Flex Serv Manuf J 25(1-2), 6-24, 2013) proposed a new model for the resource-constrained project scheduling problem. Despite its potential, the presentation of the mixed-integer programmi...
详细信息
Recently, Bianco and Caramia (Flex Serv Manuf J 25(1-2), 6-24, 2013) proposed a new model for the resource-constrained project scheduling problem. Despite its potential, the presentation of the mixed-integerprogramming model contains some ambiguity which may create misunderstanding in the implementation phase. Here, we clarify the definitions of the decision variables and illustrate their corresponding values using a numerical example. Furthermore, we propose a different interpretation of two decision variables which gives rise to an alternative model formulation also presented using the same numerical example.
The nesting problem, also known as irregular packing problem, belongs to the generic class of cutting and packing (C&P) problems. It differs from other 2-D C&P problems in the irregular shape of the pieces. Th...
详细信息
The nesting problem, also known as irregular packing problem, belongs to the generic class of cutting and packing (C&P) problems. It differs from other 2-D C&P problems in the irregular shape of the pieces. This paper proposes a new mixed-integer model in which binary decision variables are associated with each discrete point of the board (a dot) and with each piece type. It is much more flexible than previously proposed formulations and solves to optimality larger instances of the nesting problem, at the cost of having its precision dependent on board discretization. To date no results have been published concerning optimal solutions for nesting problems with more than 7 pieces. We ran computational experiments on 45 problem instances with the new model, solving to optimality 34 instances with a total number of pieces ranging from 16 to 56, depending on the number of piece types, grid resolution and the size of the board. A strong advantage of the model is its insensitivity to piece and board geometry, making it easy to extend to more complex problems such as non-convex boards, possibly with defects. Additionally, the number of binary variables does not depend on the total number of pieces but on the number of piece types, making the model particularly suitable for problems with few piece types. The discrete nature of the model requires a trade-off between grid resolution and problem size, as the number of binary variables grows with the square of the selected grid resolution and with board size. (C) 2013 Elsevier B.V. All rights reserved.
We consider a Two-Dimensional Cutting Stock Problem (2DCSP) where stock of different sizes is available, and a set of rectangular items has to be obtained through two-stage guillotine cuts. We propose and computationa...
详细信息
We consider a Two-Dimensional Cutting Stock Problem (2DCSP) where stock of different sizes is available, and a set of rectangular items has to be obtained through two-stage guillotine cuts. We propose and computationally compare three mixed-integer programming models for the 2DCSP developing formulations from the literature. The first two models have a polynomial and pseudo-polynomial number of variables, respectively, and can be solved with a general-purpose MIP solver. The third model, having an exponential number of variables, is solved via branch-and-price techniques. We conclude the paper describing the results of extensive computational experiments on a set of benchmark instances from the literature. (C) 2013 Elsevier Ltd. All rights reserved.
The second generation of optical networks with wavelength division multiplexing (WDM) is based on the notion of two layer networks, where the first layer represents a logical topology defined over the physical topolog...
详细信息
The second generation of optical networks with wavelength division multiplexing (WDM) is based on the notion of two layer networks, where the first layer represents a logical topology defined over the physical topology of optical fibers and the second layer represents multiple traffic requests combined (multiplexed) over the paths established in the logical topology. Because the design of both of these layers is challenging by itself, researchers have mainly focused on solving these problems either independently or in a sequential fashion. In this paper, we look at the WDM optical network design problem with nonbifurcated traffic flows and propose an exact branch-and-price procedure that simultaneously solves logical topology design and traffic routing over the established logical topology. The unique feature of the proposed algorithm is that it works with a row-incomplete mathematical formulation and two types of variables that exponentially grow in number with the problem size. We discuss computational issues related to the use of this procedure and propose two approximate branch-and-price procedures that can be used to obtain lower and upper bounds for this problem. Finally, we present the results of our computational experiments for two design objectives and alternative optical network settings.
The design of the distribution system is a strategic issue for almost every company. The problem of locating facilities and allocating customers covers the core topics of distribution system design. Model formulations...
详细信息
The design of the distribution system is a strategic issue for almost every company. The problem of locating facilities and allocating customers covers the core topics of distribution system design. Model formulations and solution algorithms which address the issue vary widely in terms of fundamental assumptions, mathematical complexity and computational performance. This paper reviews some of the contributions to the current state-of-the-art. In particular, continuous location models, network location models, mixed-integer programming models, and applications are summarized. 2003 Elsevier B.V. All rights reserved.
暂无评论