ARTICLE IN PRESS
European Journal of Operational Research xxx (2006) xxx–xxx www.elsevier.com/locate/ejor
Discrete Optimization
A multi-objective programming approach to 1.5-dimensional assortment problem Rafail N. Gasimov, Aydin Sipahioglu *, Tugba Sarac¸ Industrial Engineering Department, Eskisßehir Osmangazi University, Bademlik 26030, Eskisßehir, Turkey Received 30 April 2005; accepted 13 March 2006
Abstract In this paper we study a 1.5-dimensional cutting stock and assortment problem which includes determination of the number of different widths of roll stocks to be maintained as inventory and determination of how these roll stocks should be cut by choosing the optimal cutting pattern combinations. We propose a new multi-objective mixed integer linear programming (MILP) model in the form of simultaneously minimization two contradicting objectives related to the trim loss cost and the combined inventory cost in order to fulfill a given set of cutting orders. An equivalent nonlinear version and a particular case related to the situation when a producer is interested in choosing only a few number of types among all possible roll sizes, have also been considered. A new method called the conic scalarization is proposed for scalarizing non-convex multi-objective problems and several experimental tests are reported in order to demonstrate the validity of the developed modeling and solving approaches. 2006 Elsevier B.V. All rights reserved. Keywords: Cutting; 1.5-dimensional assortment problem; Multi-objective programming; Weighted sum scalarization; Conic scalarization; Mixed integer linear programming
1. Introduction The cutting stock problem and the assortment problem are two well-known related problems. The cutting stock or the cutting pattern selection problem is to determine how the stock materials (particularly, paper rolls) should be cut into the required sizes. The assortment problem, also referred to as a stock
*
Corresponding author. E-mail addresses:
[email protected] (R.N. Gasimov),
[email protected] (A. Sipahioglu),
[email protected] (T. Sarac¸).
size selection problem, involves the choice of the best combination of material sizes (particularly, paper roll sizes) or briefly stock sizes to be maintained as inventory in order to minimize an appropriate objective function(s). One of the most important characteristics used for classification of such problems, is their dimensionality. The dimensionality is the minimum number of dimensions of real numbers necessary to describe the geometry of the patterns, (Dyckhoff, 1990). One-dimensional cutting stock problem is the trim loss minimization problem in which, known quantities of rolls of various widths and the same diameter are to be slit from stock rolls of some standard width and diameter. Two-dimensional problems
0377-2217/$ - see front matter 2006 Elsevier B.V. All rights reserved. doi:10.1016/j.ejor.2006.03.016
ARTICLE IN PRESS 2
R.N. Gasimov et al. / European Journal of Operational Research xxx (2006) xxx–xxx
appear in situations where a flat material has to be divided into products of smaller rectangular measures. One-and-a-half-dimensional (1.5-dimensional) cutting stock problem is a particular case of the two-dimensional problem in which the length of a sheet is sufficiently large (infinite for practical purposes). These kinds of problems arise when rectangular pieces are laid out on a very long roll of material. Although rectangular blanks have to be cut, it is not a two-dimensional problem because trim loss along the length of the stock material is not a dimensional issue. The problem is more complex than a onedimensional problem because of the desire to match up orders both across the width and along the length dimensions. These problems and their mathematical models can be classified with respect to some characteristics such as special properties of cutting operations, the number of integer and continuous decision variables and solution methods. The conditions of the cutting operations exclusively concern the feasibility or suitability of cutting patterns. First a distinction must be made between cutting operations yielding only rectangular products and those yielding non-rectangular ones. With regard to rectangular cutting operations a further distinction can be made between cuts that are made parallel to the edges (orthogonal) or made at any angle to the latter (non-orthogonal). Orthogonal cutting patterns can be divided into two further categories. If the cutting technology enables only straight cuts to be made from one edge of the material to the opposite one, as in the case when cutting paper with cutting machines, then we speak of guillotine cutting patterns. If, however, it is permitted to discontinue the cutting at any place in the material, then non-guillotine cutting patterns can also be cut. One-and-a-half-dimensional cutting stock and/or assortment problems occur for example, in the production of corrugated boxes. Different versions of such problems have been considered by a number ¨ zdemir (2003) proposed a of authors. Sarac¸ and O multi-objective mathematical model for 1.5-dimensional assortment problem in which one of the objectives is non-convex. They suggested a genetic algorithm for solving this model involving binary variables by scalarizing it using simple weighted approach. Savsar and Cogun (1994) combined three problems in a single model: a 1.5-dimensional cutting stock problem, storage space problem and machine loading problem. They developed and solved a linear programming model for this problem which did not include the selection of stock sizes.
Chauny et al. (1987) discussed the selection of cutting pattern combinations for 1.5-dimensional problem for which 90 rotations are allowed. A detailed review of works concerning the 1.5-dimensional cutting stock problems made in 1965–1990 was given by Sweeney and Paternoster (1992). In this paper we study 1.5-dimensional cutting stock and assortment problem in which only orthogonal and non-guillotine cutting patterns are produced and all the pieces have fixed orientation. We construct a multi-objective mixed integer linear programming model for this problem in the form of simultaneously minimization of two objective functions which are related to the total trim loss cost and inventory cost respectively. An equivalent nonlinear version and a particular case related to the situation when a producer is interested in choosing only a few number of types among all possible roll sizes, have also been considered. A new method called the conic scalarization is proposed for scalarizing non-convex multi-objective problems and several experimental tests based on the real life problem have been generated and solved by using both weighted and conic scalarization approaches in order to demonstrate the validity of the developed modeling and solving approaches. Recently a new and improved typology which is different from the Dychoff’s one is introduced by Wa¨scher et al. (2005). By this typology, cutting and packing problems are classified using five criteria, namely ‘‘dimensionality’’, ‘‘kind of assignment’’, ‘‘assortment of large objects’’, ‘‘assortment of small items’’, and ‘‘shape of the small items’’. Taking into account the explanations presented above, we can claim that the problems considered in this paper are open dimension (with more than one large object) and cutting stock (with a strongly heterogeneous assortment of large objects) problems of input minimization type. To our best knowledge, open dimension problems with more than one large object have not been discussed in the area of cutting and packing problems earlier. The rest of the paper is outlined as follows. In Section 2, the assortment problem under study is formulated in detail and a multi-objective optimization model which uses two objective functions is presented. In Section 3 we show how to reduce the solution of the model to the scalar problem. In this section the conic scalarization method along with the main scalarization theorems and the formulations of the scalarized problems are presented. In Section 4 different examples are formulated and computational results with corresponding interpre-
ARTICLE IN PRESS R.N. Gasimov et al. / European Journal of Operational Research xxx (2006) xxx–xxx
tations are reported. Section 5 draws some conclusions from the study. 2. Problem formulation and the mathematical model One of the main problems faced in the corrugated box industry is the planning and scheduling of production. In the problem of corrugated box production that we consider in this paper, an optimal number of paper rolls with certain sizes among all the standard roll sizes existing in the market have to be selected. During the planning period the selected rolls will be used for cutting n known order pieces having definite rectangle forms. These pieces are produced and rectangularly cut by corrugator. The amount of corrugator side trim is a significant number because, in the majority of cases, it is the second largest item in the controllable waste. For example, if a plant cuts up 40 000 tons of roll stock annually, 2.5% side trim is equal to 1000 tons and the minimum cost of US$ 325 000 per year (Cloud, 1994). Therefore, it becomes very important to construct a mathematical model which optimizes the cutting procedure. Determining the cutting pattern combinations is an important phase in the modeling of a cutting stock problem where these cutting patterns are used in order to fulfill the order pieces required for some planning period. Note that, an instruction that lists the order pieces to be cut from one unit of a paper roll is called a cutting pattern. We number all the order pieces by taking into account only their widths. Due to a 1.5-dimensional nature of the problem under consideration, the length of each order piece actually represents the sum of lengths of all order pieces with the same width. These pieces can be cut by different ways by using different cutting pattern combinations and paper rolls having different sizes. Cutting patterns represent all cutting combinations for all the existing order pieces and for all the roll sizes which do not include the information about the lengths of order pieces. The choosing of a roll size with the corresponding cutting pattern combination is very important in minimizing the trim loss. For example, if we have order pieces with 600 mm and 700 mm widths, then we will have cutting patterns 2 · 600 + 1 · 700, 3 · 600 + 1 · 700, 1 · 600 + 2 · 700, 4 · 600, and so on. If the roll with 2500 mm width is used, then the trim loss amounts corresponding to these cutting patterns will be 2500 (2 · 600 + 1 · 700) = 600 mm, 2500 (3 · 600 +
3
1 · 700) = 0 mm, 2500 (1 · 600 + 2 · 700) = 500 mm, and 2500 (4 · 600) = 100 mm, respectively. As it can be seen from this example, with increasing number of different roll sizes the material utilization generally improves, and consequently the total trim loss cost decreases. On the other hand, a larger number of different stock sizes results in more frequent changes in the stock sizes being cut and requires an increase in the number of different stock locations. The costs of operation, stocking and handling, therefore, generally increase with increasing the number of stock sizes. We assume that all these costs may be combined and we will call it a combined inventory cost. We also assume that for each type of roll sizes existing in the market, all the cutting patterns and corresponding (side) trim loss amounts are known. In this case, the problem is to select the optimal number of roll sizes have to be stocked and to select the corresponding cutting patterns in order to produce the required order pieces which has to be cut from the selected rolls by simultaneously minimizing the total trim loss cost and the combined inventory cost. For formulating the mathematical model of this problem the following notations related to cutting orders, roll sizes and cutting patterns are introduced. Sets and parameters Let m
be the number of all paper roll sizes, which are available for the producer n be the number of all order pieces with different widths to be fulfilled during the planning period p be the number of all cutting patterns I = {1, 2, . . . , m} denotes the set of all roll sizes J = {1, 2, . . . , n} denotes the set of all order pieces K = {1, 2, . . . , p} denotes the set of all cutting patterns dj be the length of order piece j, (in meters), j2J ajk be the total number of order piece j contained in cutting pattern k, j 2 J, k 2 K fik be the side trim loss from roll i and cutting pattern k, (in meters), j 2 J, k 2 K c be the price of the unit square meter of the paper ci be the combined inventory cost corresponding to paper roll i 2 I U be a large positive constant, which can also P be calculated as U ¼ j d j
ARTICLE IN PRESS 4
R.N. Gasimov et al. / European Journal of Operational Research xxx (2006) xxx–xxx
Decision variables Let, be the length of the paper has to be cut from roll i using the cutting pattern k, (in meters), i 2 I, k 2 K be 1, if the roll size i is chosen; and 0 otherwise, i 2 I
xik
yi
Objective functions We have two objective functions: • Total trim loss cost: F 1 ðx; yÞ ¼
p X m X k¼1
c fik xik .
ð1Þ
m X
ci y i .
ð2Þ
i¼1
Under these notifications we can formulate a multiobjective MILP model for the 1.5-dimensional cutting stock and assortment problem (P) described above, in the following form: min
2.1. A nonlinear model In the model (P), the constraint set (5) serves only for the connection between cutting patterns and the roll sizes have to be selected. Actually, the demand satisfaction constraints (4) can be reformulated without using these constraints. Namely, the constraints (4) and (5) can be unified and expressed by the single set in the following form: p X m X ajk xik y i ¼ d j ðj ¼ 1; . . . ; nÞ. k¼1
i¼1
• Combined inventory cost related to all paper rolls which are decided to be used in the planning period: F 2 ðx; yÞ ¼
Note that the problem (3)–(7) would be linear except for constraints (7). This model becomes non-convex again because of these constraints which causes difficulties in the solution process (see Section 3).
½F 1 ðx; yÞ; F 2 ðx; yÞ
ð3Þ
i¼1
In this case the new demand satisfaction constraints become nonlinear and a multi-objective MINLP model for the 1.5-dimensional cutting stock and assortment problem (P1) can equivalently be formulated in the following form: min ½F 1 ðx; yÞ; F 2 ðx; yÞ ð3Þ subject to p X m X ajk xik y i ¼ d j ðj ¼ 1; . . . ; nÞ; k¼1 i¼1
ð8Þ xik P 0 ði ¼ 1; . . . ; m; k ¼ 1; . . . ; pÞ; ð6Þ
subject to p X m X k¼1
ajk xik ¼ d j
y i 2 f0; 1g ði ¼ 1; . . . ; mÞ;
ðj ¼ 1; . . . ; nÞ;
ð7Þ
i¼1
ð4Þ p X
xik 6 U y i
ði ¼ 1; . . . ; mÞ;
ð5Þ
Although the demand satisfaction constraints in the (P1) model are nonlinear, it is remarkable that it adopts fewer constraints than the linear model (P).
k¼1
xik P 0
ði ¼ 1; . . . ; m; k ¼ 1; . . . ; pÞ;
y i 2 f0; 1g
ði ¼ 1; . . . ; mÞ.
ð6Þ ð7Þ
Constraint set (4) ensures that the demand for any order piece has to be met. If any cutting pattern is used for a roll size i, constraint set (5) forces yi = 1. On the other hand, the minimization of the second objective function expressing a combined inventory cost will force the number of different roll sizes to decrease. In the case when no cutting pattern is used for a roll size i then this situation naturally will lead to yi = 0.
2.2. Particular case In this section we consider a particular case of the assortment problem described above, related to the situation when the producer is interested in choosing only a few number of types among all the possible m roll sizes. In this case the problem becomes to determine which S roll sizes and how many of each size should be stocked in order to minimize the total trim loss cost and to fulfill the order pieces during the planning period. For this model the number of different roll sizes to be kept as inventory can be treated as a parameter.
ARTICLE IN PRESS R.N. Gasimov et al. / European Journal of Operational Research xxx (2006) xxx–xxx
Let, S be the number of different types of standard lengths to be selected from m possible roll sizes. The formulation of the MILP model (P2) corresponding to this case is given below: F 1 ðx; yÞ
min
ð9Þ
subject to m X
y i 6 S;
ð10Þ
ðx; yÞ 2 X ;
ð11Þ
i¼1
where X ¼ fðxi;k ; y i Þ; i ¼ 1; . . . ; m; k ¼ 1; . . . ; p : constraints (4)–(7) are all satisfiedg;
ð12Þ
3. Solution approaches Solution approaches for cutting stock and assortment problems can generally be divided into three categories: heuristic methods (see for example, Holthaus, 2003; Beasley, 2004), exact methods (Savsar and Cogun, 1994) and hybrid approaches (Chauny et al., 1987). In this paper we study exact solution approach for solving the models constructed. Exact solution approaches used for solving such problems generally have two main difficulties. The first of them is related to the solution time, which increases exponentially with the number of integer decision variables and the second one is the non-convexity of the problem which again is a result of the existence of integer variables, even though the objective and constraint functions in such models are all linear. Because of the multi-objective nature of the models (P) and (P1), a solution process of these problems has been considered in two stages: (1) The scalarization of the given problem, and (2) The solution of the scalarized problem. Since the problems (P) and (P1) are both non-convex a special approach for their scalarization is implemented (see, Section 3.1). The solution approach for (P2) and the scalarized versions of (P) and (P1) have been explained in Section 3.2. 3.1. Scalarization Scalarization means combining different objectives to a single one such that the obtained single
5
objective optimization problem allows to find (all) Pareto (or properly) efficient solutions of the initial multi-objective problem. There are many scalarization methods for combining different objectives to a single one (see, for example, Luc, 1989; Chankong and Haimes, 1983; Ehrgott, 2005). We use here a scalarization approach suggested by Gasimov (see, Gasimov, 2001) and explain how it can be used to formulate scalar optimization problems allowing calculating all the efficient solutions. Gasimov introduced an explicit class of increasing convex functions which serve for combining different objectives to a single one without any restrictions on objectives and constraints of the problem under consideration, such as convexity and/or boundedness. These functions were used to characterize Benson proper efficient solutions of non-convex multiobjective problems in terms of saddle points of scalar Lagrangian functions introduced in the paper. Besides, this approach preserves convexity, if the initial problem has such a property. Note that it has successfully been applied to a multi-objective 0–1 faculty course assignment problem studied by ¨ zdemir and Gasimov (2004). O Now we briefly present some definitions and two main results from Gasimov (2001). Let R2þ ¼ fðy 1 ; y 2 Þ 2 R2 jy 1 P 0; y 2 P 0g. Definition 1. Let S be a non-empty subset of R2. (a) An element s 2 S is called a Pareto minimal element of the set S, written s 2 min(S), if ðfsg R2þ Þ \ S ¼ fsg. (b) An element s 2 S is called a properly minimal element of S (in the sense of Benson), written s 2 p min(S), if s is a Pareto minimal element of S and the zero element of R2 is a Pareto minimal element of cl cone ðS þ R2þ fsgÞ, where cl denotes the closure of the set and cone(S) :¼ {ksjk P 0 and s 2 S}. Note that the problem (P) can also be formulated in the form: min ½F 1 ðx; yÞ; F 2 ðx; yÞ;
ðx;yÞ2X
where X is the set of feasible solutions defined in (12). Let F(x, y) = (F1(x, y), F2(x, y)), and let F(X) be the image of X. Definition 2. ðx; y Þ 2 X is called a Pareto efficient solution of (P) if F ðx; y Þ 2 minðF ðX ÞÞ; ðx; y Þ 2 X is
ARTICLE IN PRESS 6
R.N. Gasimov et al. / European Journal of Operational Research xxx (2006) xxx–xxx
called a proper efficient solution of (P) (in the sense of Benson), if F ðx; y Þ 2 p minðF ðX ÞÞ. Let W :¼ fða; wÞ 2 R R2 j0 6 a < minfw1 ; w2 g; w1 ; w2 > 0g.
ð13Þ
Theorem 1. Suppose that for some (a, w) 2 W an element ðx; y Þ 2 X is an optimal solution to the following scalar minimization problem: " # 2 2 X X min a jF i ðx; yÞj þ wi F i ðx; yÞ . ð14Þ
ðx;yÞ2X
i¼1
i¼1
Then the pair ðx; y Þ 2 X is a proper efficient solution of (P). Theorem 2. Suppose ðx; y Þ 2 X is a proper efficient solution of (P). Then there exists a triple (a, w1, w2) 2 W, such that ðx; y Þ 2 X is an optimal solution to the following scalar minimization problem: ( min
ðx;yÞ2X
a
2 X
jF i ðx;yÞ F i ðx;y Þj þ
i¼1
2 X
) wi ½F i ðx; yÞ F i ðx;y Þ .
i¼1
ð15Þ
Theorem 1 asserts that any solution of the (scalar) problem (14) is an efficient solution of the problem (P). On the other hand Theorem 2 claims that every efficient solution ðx; y ) of (P) can be calculated by solving a scalar problem of the form (15) for some triple (a, w1, w2) 2 W. Thus, these theorems assert that the problem (P) can be scalarized in the form (14) and/or (15), and all efficient solutions of (P) can be calculated by solving scalar problems of the form (14) or (15). In non-convex multi-objective programming the distinction between the so-called supported and non-supported efficient solutions is very important. An efficient solution ðx; y Þ is called supported (with respect to hyperplanes), if there is a ðw1 ; w2 Þ 2 R2> ¼ fðw1 ; w2 Þ : w1 > 0; w2 > 0g such that ðx; y Þ is an optimal solution to min
ðx;yÞ2X
2 X
wi F i ðx; yÞ.
i¼1
It is well-known (Geoffrion, 1968) that if X is convex and both Fi, i = 1, 2 are convex functions, then all Benson proper efficient solutions are sup-
ported, see e.g. (Ehrgott, 2005). However, for nonconvex problems there exist non-supported efficient solutions. It is obvious that if ðx; y Þ is an efficient solution and if there is some k with k 2 [0, 1] such that F k ðx; yÞ ¼ kF ðx1 ; y 1 Þ þ ð1 kÞF ðx2 ; y 2 Þ < F ðx; y Þ for some (x1, y1), (x2, y2) 2 X then ðx; y Þ is not an optimal P2solution to the weighted sum problem minðx;yÞ2X i¼1 wi F i ðx; yÞ. In other words, this means that efficient solution ðx; y Þ can not be calculated using the weighted sum scalarization method. The significance of Theorems 1 and 2 is that they can be used to calculate the possible non-supported efficient solutions. However, it is not clear how in practice these theorems can be used to meet the need for decision maker, i.e. how the efficient solutions corresponding to decision makers preferences can be generated. Regarding Theorem 1, or the solutions of problem (14), note that in the case when the signs of objective functions remain unchanged on the whole set of feasible solutions, then the absolute values in (14) are not sensible in the whole expression and it becomes to the expression representing the weighted sum scalarization. This situation can be overcome by considering the shifted multi-objective problem: min ½F 1 ðx; yÞ B1 ; F 2 ðx; yÞ B2 ;
ðx;yÞ2X
ð16Þ
where B1 and B2 are arbitrary fixed numbers. It is evident that the initial problem min ½F 1 ðx; yÞ; F 2 ðx; yÞ
ðx;yÞ2X
and (16) have the same set of efficient solutions. Therefore, by choosing the numbers B1 and B2 from the interior of ranges of F1 and F2 respectively, we can replace the objective functions by new ones in order to make the absolute values used in the scalarized problem (14) sensible. By taking different values for B1 and B2 one can obtain different efficient solutions by solving the scalarized version of the problem (16) of the following form: ( ) 2 2 X X min a jF i ðx; yÞ Bi j þ wi ½F i ðx; yÞ Bi .
ðx;yÞ2X
i¼1
i¼1
ð17Þ Since the problem under consideration involves integer variables, the model naturally becomes non-convex. In this situation decision maker may not be sure whether all the efficient points (or solutions) corresponding to his (her) own preferences (weights w1 and w2) are found by using weighted
ARTICLE IN PRESS R.N. Gasimov et al. / European Journal of Operational Research xxx (2006) xxx–xxx
sum scalarization. To seek the possible non-supported or ‘‘hidden’’ efficient points, the parameters B1 and B2 initially can arbitrarily be chosen between the neighbor supported Pareto optimal points that correspond to his (her) weight(s), and are ‘‘relatively distant’’ from each other. After calculating additional efficient points, the intervals for choosing the non-zero values for B1 and B2 in (17) can sequentially be tightened and decision maker can find other non-supported efficient solutions (if they exist) by this way. Considering this discussion, we can formulate the following corollary which completely characterizes Benson proper efficient solutions. Corollary 1. A feasible solution ðx; y Þ 2 X is Benson proper efficient if and only if there are (a, w1, w2) 2 W and B1, B2 2 R such that ðx; y Þ 2 X is an optimal solution to (17). A proof of the corollary can easily be obtained from Theorems 1 and 2. Geometrically, the level sets of the scalarization function used in (17), are convex cones in R2 which include the ordering cone R2þ . Changing the parameters (a, w1, w2) 2 W and B1, B2 causes in changing the form and the place of the vertex of these cones and therefore by minimizing the problem (17) for different sets of these parameters one can find different efficient points in the image set supported by these cones. Since the method is based on finding efficient solutions by characterizing them as supporting points of the image set with respect to cones, we call it a conic scalarization method. Note that for a = 0 expression in (17) reduces to the weighted sum scalarization min
ðx;yÞ2X
2 X
wi F i ðx; yÞ.
i¼1
Therefore non-supported ‘‘hidden’’ efficient solutions can only be found with a > 0. 3.2. Solving the scalarized problems The models (P), (P1) and (P2) developed in this paper and the scalarized problems of the form (17) are all linear and/or nonlinear integer optimization problems involving binary variables. It is wellknown that existence of binary variables causes serious difficulties in solution process of such problems. A significant feature of these models is that they are constructed by using a less number of binary vari-
7
ables which seriously affects their solution time. The solvability of such problems using standard solvers has been demonstrated on test problems presented in the next section, where we construct examples with 10, 30, 50 and 80 order pieces and 41 different sizes of paper rolls. The scalarized versions of all test problems corresponding to (P) and (P1) and also test problems corresponding to (P2) have been solved using GAMS 20.7 software, Brooke et al. (1998). 4. A problem description and computational results In this section we consider a 1.5-dimensional cutting stock and assortment problem studied in the corrugated box factory in Eskisßehir, Turkey. The firm, in which this study was realized, produces 4000 different types of corrugated carton boxes by using different sizes of paper rolls. These boxes correspond to the rectangular pieces which we call products and which have to be cut. There are many products with equal width and different length among these 4000 types. Due to the 1.5 nature of the problem under consideration, all the products having the same width can be combined and be considered as a single product with the total length equal to the sum of all lengths of these products. A number of ‘‘different’’ products can significantly be reduced by applying this way. Considering this situation, we have generated four test problems by selecting 10, 30, 50 and 80 types of products with the highest demand level from the existing different types of corrugated carton boxes. In the sequel we will use the notions 10-, 30- 50- and 80-product problems for identifying the corresponding test problems with 10, 30, 50 and 80 types of products. There are 41 different sizes of paper rolls with widths 210 cm, 211 cm, . . . , 250 cm, numbered from i = 1–41 respectively, among which it has to be made a selection. Cutting patterns are generated by taking into account the general technical conditions of the factory and also constraints related to the corrugator’s abilities. The constraints which depend on technical abilities of the corrugator are: • The maximum number of different types of order pieces can be produced at the same time is two. • The maximum number of strips can be cut simultaneously is eight. • Minimum and maximum values of the trim loss have to be 3 cm and 10 cm respectively.
ARTICLE IN PRESS 8
R.N. Gasimov et al. / European Journal of Operational Research xxx (2006) xxx–xxx
Besides, there are many products having different order dates in the same planning period. Such products are desired to be produced in different dates. Therefore two different order pieces which have different order dates should not be located in the same cutting pattern. Regarding this situation, in solving the test problems considered here, order pieces that have higher and continuous demand are allowed to be in the same cutting pattern. Due to these special conditions existing in the corrugated box factory, the number of possible cutting patterns is reduced significantly. Cutting patterns satisfying the above mentioned constraints are generated applying a computer program coded in Excel/Visual Basic Application which evaluates the all possible combinations. By using this macro, 84, 465, 937 and 1929 cutting patterns are generated for 10-, 30-, 50- and 80-product test problems respectively. This leads to 41 binary variables in all problems and, for example, 1929 · 41 = 79 089 real variables in 80-product problem. Pareto efficient solutions of test problems corresponding to (P) and (P1) are calculated by firstly scalarizing them using both weighted and conic scalarization approaches and then solving the scalar problems using GAMS solvers. As it follows from the scalarization formulas (14), (15) or (17), the difference between these two approaches is in the existence of the first terms in brackets (a times the sum of absolute values). When a 5 0 this term provides supporting the image set of the problem under consideration by cones instead of hyperplanes. By changing the set of parameters (a, w1, w2) 2 W (see (13)), one can obtain different supporting cones and therefore can calculate different Pareto and properly minimal elements and different efficient solutions respectively, and also those which cannot be calculated using simple weighted scalarization. To compare the performances of the conic and weighted scalarization approaches we have calculated solutions corresponding to different sets of parameters (a, w1, w2) 2 W with a = 0 and a 5 0 for all the test problems corresponding to (P) and (P1) separately. Both of these problems have firstly been scalarized by using simple weighted scalarization approach for w1, w2 = 0, 1, 2, . . . , 50 with w1 + w2 = 50 and a corresponding set of Pareto efficient elements and solutions has been generated by solving them. Thereafter, the scalarization formula (17) has been utilized for specifically selected numbers B1, B2 and a 5 0, and new Pareto efficient solu-
tions have been calculated for all the test problems corresponding to (P) and (P1). It has graphically been demonstrated that these new solutions could not be obtained using only the simple weighted scalarization approach. All the test problems corresponding to (P2) have been solved for values of the parameter S = 1,2, . . . , 5 separately. All the scalarized problems have been solved using GAMS/DICOPT solver. Due to the linearity of the problem (P2), the corresponding test problems have been solved using GAMS/CPLEX solver. All the GAMS codes have been implemented on HP XW6000 workstation with two Intel Xeon processors. Computational results for all test problems are presented in the following subsection. The following notations and parameters were used to summarize the results. • F1 is the first objective function which indicates a total trim loss cost, see (1). • F2 is the second objective function which indicates a combined inventory cost related to a total number of paper rolls decided to be used in the planning period, see (2). • (P) is the general multi-objective mixed integer linear programming problem with objectives F1 and F2 and constraints (4)–(7). • (P1) is the multi-objective mixed integer nonlinear programming problem with the same objectives as in (P) and constraints (6)–(8). • (P2) is the single objective mixed integer linear programming problem with the objective F1 and constraints (9)–(11). This problem corresponds to a particular case in which the maximal number of standard lengths that has to be selected is fixed. • w1 and w2 are weights of objectives which correspond to preferences of decision maker used in the scalarization of multi-objective problems (P) and (P1). • a is a coefficient of norm term used in the conic scalarization. • S is the number of different types of standard lengths to be selected from m possible roll sizes.
4.1. Computational results for 10-product problems Computational results for 10-product weighted scalarized problem corresponding to (P) are presented in Table 1.
ARTICLE IN PRESS R.N. Gasimov et al. / European Journal of Operational Research xxx (2006) xxx–xxx Table 1 Computational results obtained using weighted sum scalarization for 10-product linear problem (P) w1
w2
F1
F2
i: yi = 1
0 1–15 16–25 26–35 36–38 39–41 42–43 44 45–47 48–49 50
50 49–35 34–25 24–15 14–12 11–9 8–7 6 5–3 2–1 0
561.58 53.59 19.2 15.83 15.21 14.17 10.93 10.53 10.35 8.95 8.94
5 5.5 21.5 25 26.5 30 47 49.5 51 75 615
1 2 2, 2, 2, 4, 4, 4, 4, 4, 4,
23 30 33 38 22, 30, 30, 30, 21,
41 38 41 39, 41 23, 25, 38, 39, 41
It can be seen from Table 1 that in the situation when only the second objective will be minimized, i.e. when w1 = 0, w2 = 50 only one roll has been chosen by the model (i = 1 for which yi = 1). In this situation the value of the first objective function related to the trim loss cost is very large, because all the efforts of the model are used to minimize the second objective function related to a total number of paper rolls decided to be used in the planning period. For all the pairs of weights (1, 49), (2, 48), . . . , (15, 35) the same optimal solution with F1 = 53.59, F2 = 5.5 is obtained. In all the solutions corresponding to these weights the second paper roll is chosen (i = 2 for which yi = 1). It is remarkable that the optimal value of the first objective function related to the trim loss cost decreases with its increasing ‘‘weight’’ (the value of w1) in the total weighted sum whereas the number of paper rolls increases. Computational results for 10-product problem corresponding to (P) scalarized using the formula (17) for different values of the parameters (a, w1, w2) 2 W and B1 = 40, B2 = 15 are presented in Table 2a. These values for B1 and B2 have been selected between the Pareto optimal points (53.59, 5.5) and (19.2, 21.5) which are presented in the second and third rows in Table 1. (For more detailed explanations see Section 3.1.) We utilized formula (17) for all possible integer triples (a, w1, w2) 2 W with w1,
Table 2a Additional Pareto minimal points found by solving 10-product linear problem (P), using conic scalarization for B1 = 40, B2 = 15 a
w1
w2
F1
F2
i: (yi = 1)
8 4 1
13 15 16
37 35 34
39.91 31.78 30.05
15 16 16.5
1, 11 1, 13 2, 13
9
w2 = 1, 2, . . . , 50, w1 + w2 = 50 and a = 1, 2, . . . , min{w1, w2}. Note that only the results which are different from those presented in Table 1 are presented in Table 2a. Table 2a presents additional Pareto efficient solutions found using formula (17). For example, the efficient values F1 = 53.59, F2 = 5.5 with i = 2 is reported in Table 1 which is found using weighted sum scalarization method for the weights w1 = 13 and w2 = 37. By using formula (17) with B1 = 40, B2 = 15, a = 8 and the same weights, new efficient values F1 = 39.91, F2 = 15 with optimal roll size numbers i = 1 and i = 11 are found. This exactly corresponds to situation in which decision maker does not sure if all the Pareto efficient solutions are found using the weighted sum scalarization and he/she wants to seek if any other efficient solution exists. In Table 2a three alternative solutions for different pairs of weights are reported. Now, as it was explained in Section 3.1, the possible interval for choosing the new B1 and B2 values can be tightened by using these new solutions. That is, additional Pareto efficient solutions can be found (if so exist) by choosing new B1, B2 values from the interval (30.05, 16.5) and (19.2, 21.5). Note that, new efficient solution for B1 = 25, B2 = 20, a = 12 and weights (14, 16) is found and reported in Table 2b. Fig. 1 demonstrates that the three of four newly calculated Pareto minimal points presented in Tables 2a and 2b namely the points (39.91, 15), (31.78, 16), (22.59, 21) are ‘‘behind’’ the straight line passing through the two Pareto minimal points (53.59, 5.5) and (19.2, 21.5), which means that they could not be calculated by using simple weighted scalarization approach. By a similar way, other ‘‘hidden’’ Pareto minimal points can be calculated by choosing different values for B1 and B2 from other intervals. For example, new Pareto minimal points calculated for B1 = 12 and B2 = 38 are reported in Table 2c. These values for B1 and B2 are chosen between the Pareto efficient points (14.17, 30) and (10.93, 47) presented in the sixth and seventh rows respectively, in Table 1. We have also tested the solvability of the nonlinear model (P1). Notice that this model has been conTable 2b Additional Pareto minimal points found by solving 10-product problem (P), using conic scalarization for B1 = 25, B2 = 20 a
w1
w2
F1
F2
i: (yi = 1)
Time (seconds)
12
14
36
22.59
21
2, 22
11.03
ARTICLE IN PRESS 10
R.N. Gasimov et al. / European Journal of Operational Research xxx (2006) xxx–xxx 23
(19,2;21,5)
21
(22,59;21)
19 17
(30,05;16,5)
(31,78;16)
15
(39,91;15)
13 11 9 7 (53,59;5,5)
5 15
20
25
30
35
40
45
50
55
60
Fig. 1. New Pareto minimal points calculated for 10-product test problem (P) found by using conic scalarization with B1 = 40, B2 = 15.
Table 2c Additional Pareto minimal points found by solving 10-product problem (P), using conic scalarization for B1 = 12, B2 = 38 a
w1
w2
F1
F2
i: (yi = 1)
2 2
42 41
8 9
12.83 13.75
38.5 32.5
4, 8, 38 1, 4, 33
structed using nonlinear constraints which allowed us to significantly reduce the total number of constraints. In order to compare solution times, we solved both models (P) and (P1) using the same set of parameters (a, w1, w2) 2 W and B1 = 40, B2 = 15. It is remarkable that the nonlinear problem (P1) could not be solved without using an initial solution and we have obtained different Pareto efficient solutions using different initial values. The corresponding results and solution times are presented in Table 3. As it can be seen from Table 3, an optimal solution for the linear problem (P) is found without using any initial solution. Besides, the different optimal solutions for the nonlinear problem (P1), corresponding to different initial values chosen randomly, have been found in shortest times. It is remarkable that an optimal solution has been
obtained even if initial solutions are not feasible, for example the values presented at the 2nd, 4th, 5th and 6th lines of the table are not integer. Note that optimal solutions which are completely different from the chosen initial ones could also be obtained; see for example lines 3, 4 or 6. Note also that the solutions obtained for nonlinear problem reported at lines 2–5 are all new and have not been reported in Table 1. Computational results for 10-product problem (P2) defined by (9)–(12), corresponding to five different values of the parameter S are presented in Table 4, where S is the given number of different types of standard lengths to be selected from m possible roll sizes. Note that the problem (P2) can be considered as a problem obtained from the two-objective one by Table 4 Computational results for 10-product problem (P2) S
F1
i: yi = 1
Time (seconds)
1 2 3 4 5
24.96 13.98 10.35 8.95 8.94
41 8, 38 4, 30, 41 4, 30, 39, 41 4, 30, 38, 39, 41
1.31 1.83 0.89 0.22 0.19
Table 3 Comparison of results for 10-product models (P) and (P1) corresponding to different initial solutions Model
Initial solution
a
w1
w2
F1
F2
i: (yi = 1)
Time (seconds)
P P1 P1 P1 P1 P1
– y1 = y11 = 0.2 y5 = y11 = 1 y5 = y15 = y25 = y35 = 0.9 y1 = y11 = y21 = y31 = 0.9 y1 = y11 = y21 = y31 = y41 = 0.9
8 8 8 8 8 8
13 13 13 13 13 13
37 37 37 37 37 37
39.91 50.52 51.43 51.43 32.48 53.59
15 10.5 12 12 20 5.5
1, 1, 1, 1, 1, 2
9.95 1.33 1.33 17.9 14.93 21.67
11 2 5 5 21
ARTICLE IN PRESS R.N. Gasimov et al. / European Journal of Operational Research xxx (2006) xxx–xxx
transforming one of the objectives (in this case F2) to the constraint set by using a fixed (upper) bound for it. It is well-known that the solutions obtained for this problem may or may not be Pareto efficient for the initial two-objective one. It is noticeable that only the solution presented at the 4th line of Table 4 is reported in the Table 1 which is found for the weights w1 = 48, w2 = 2 and w1 = 49, w2 = 1. 4.2. Computational results for 30-product problems In this section we present computational results for 30-product test problems. The computational results for linear problem (P) obtained by the weighted scalarization approach are presented in Table 5. As it can be seen from Table 5, the Pareto efficient points (625.81, 14.5) and (468.68, 20.25) corresponding to the weights (1, 49) and (2, 48) are ‘‘far’’ from each other. Since the problem has non-convexity due to integer variables, there may be solutions that are not found by weighted scalarization. By choosing the numbers B1 between 625.81 and 468.68, and B2 between 14.5 and 20.25 we try to solve a scalarized problem (17) for the same weights (1, 49) and (2, 48). Since a parameter a cannot be greater than any weight (see (13)) we consider only the values a = 1 for the weights (1, 49), and a = 1, 2 for the weights (2, 48). Two alternative solutions obtained are reported in Table 6a.
Table 5 Computational results obtained using weighted sum scalarization, for 30-product linear problem (P) w1
w2
F1
F2
i: yi = 1
0 1 2–7 8–15 16–20 21–22 23–26 27–31 32 33–34 35 36–41 42–44
50 49 48–43 42–35 34–30 29–28 27–24 23–19 18 17–16 15 14–9 8–6
78 549.15 625.81 468.68 398.92 386.17 367.46 357.46 351.1 350.25 344.36 343.04 341.87 336.94
5 14.5 20.25 32.75 38.25 51.25 59.5 66.75 68.25 79 82 85 107.75
45–49
5–1
333.82
131.5
50
0
333.36
410
1 2, 18 2, 41 2, 31, 41 1, 4, 31, 41 1, 4, 29, 35, 41 1, 4, 14, 29, 35, 41 4, 14, 24, 34, 36, 41 4, 24, 26, 29, 35, 41 4, 14, 24, 29, 35, 36, 41 4, 24, 26, 29, 35, 36, 41 4, 24, 29, 35, 36, 38, 41 4, 24, 26, 28, 29, 35, 36, 37, 41 4, 24, 26, 29, 35, 36, 37, 38, 39, 41 4, 5, 8, 24, 26, 27, 29, 34, 35, 36, 37, 38, 39, 41
11
Table 6a Additional Pareto minimal points found by solving 30–product problem (P), using conic scalarization for B1 = 500, B2 = 17 a
w1
w2
F1
F2
i: (yi = 1)
1 2
1 2
49 48
536.33 511.37
17.75 19
2, 31 2, 36
Table 6b Additional Pareto minimal points found by solving 30-product problem (P), using conic scalarization for B1 = 375, B2 = 45 a
w1
w2
F1
F2
i: (yi = 1)
14 9 3
19 19 19
31 31 31
375.62 376.4 377.43
47.5 46 44.75
1, 4, 14, 35, 41 2, 29, 36, 41 1, 26,35, 41
By considering the Pareto efficient points (386.17, 38.25) (corresponding to the weights from (16, 34) to (20, 30) in Table 5) and (367.46, 51.25), (corresponding to the weights (21, 29) and (22, 28) in Table 5) the scalarized problem (17) has been solved for B1 = 375, B2 = 45, w1 = 19, w2 = 31. Three alternative solutions found are reported in Table 6b. Geometrical interpretation corresponding to the alternative solutions reported in Table 6a is presented in Fig. 2. We have solved the conically scalarized version of nonlinear problem (P1) taking B1 = 500 and B2 = 17, for randomly chosen different initial solutions. Corresponding results and solution times are reported in Table 7. Table 7 demonstrates that new and different solutions can be found by solving the nonlinear model (P1) for the same scalarization parameters (a, w1, w2) beginning with different initial solutions. It is remarkable that the solutions reported at the lines 3, 4, 5 and 6 of Table 7, are all new, i.e. none of these solutions are reported in Tables 5 and 6a. Computational results for different S values for the problem (P2) are presented in Table 8. Note that only the solution presented at the 2nd line of Table 8 is reported in Table 5 as a Pareto efficient solution, which is calculated for the weights from w1 = 2, w2 = 48 to w1 = 7, w2 = 43. 4.3. Computational results for 50-product problems In this section we present computational results for 50-product test problems. The computational results for (P) obtained by the weighted scalarization approach are presented in Table 9.
ARTICLE IN PRESS 12
R.N. Gasimov et al. / European Journal of Operational Research xxx (2006) xxx–xxx 21 (468, 68; 20, 25)
20
(511, 37; 19)
19 18
(536 ,33 ; 17,75)
17 16 15 (62 5,81; 14, 5)
14 400
450
500
550
600
650
Fig. 2. New Pareto minimal points calculated for 30-product test problem (P) found by using conic scalarization with B1 = 500, B2 = 17.
Table 7 Comparison of results for 30-product models (P) and (P1) obtained using conic scalarization approach for B1 = 500, B2 = 17 and different initial solutions Model
Initial solution
a
W1
w2
F1
F2
i: (yi = 1)
Time (seconds)
P P1 P1 P1 P1 P1
– y2 = y36 = 0.9 y1 = y41 = 0.2 y1 = y20 = y41 = 0.9 y2 = y40 = 0.2 y2 = 0.9
2 2 2 2 2 2
2 2 2 2 2 2
48 48 48 48 48 48
511.37 511.37 553.73 553.73 580.76 4106.55
19 19 20 20 20 5.25
2, 2, 1, 1, 2, 2
289.33 12.8 18.53 128.17 18.41 1.66
Table 8 Computational results for 30-product problem (P2) S
F1
i: yi = 1
Time (seconds)
1 2 3 4 5
844.71 468.68 397.69 376.00 357.85
31 2, 41 2, 36, 41 26, 34, 37, 41 24, 26, 29, 35, 41
22.235 100.093 121.062 109.14 56.015
36 36 41 41 40
Computational results for the linear problem (P) obtained using the conic scalarization approach for different B1 and B2 and a, w1 and w2 are presented in Tables 10a and 10b, respectively and the corresponding geometrical interpretation is presented in Fig. 3. Note that the pair (F1, F2) = (3133.302, 5) found by using the conic scalarization for a = 15,
Table 9 Computational results obtained using weighted sum scalarization, for 50-product linear problem (P) W1
w2
F1
F2
i: yi = 1
0 1–4 5–20 21–27 28–36 37–39 40–43 44–45 46 47 48 49 50
50 49–46 45–30 29–23 22–14 13–11 10–7 6–5 4 3 2 1 0
13661.42 166.91 91.03 82.71 74.57 70.82 68.83 67.52 65.96 64.64 64.4 63.63 63.55
5 5.38 13.25 19.25 29.13 39.63 46.88 56.25 72.38 91.75 97.13 126.13 214.75
1 4 2, 1, 1, 5, 5, 5, 5, 9, 4, 4, 4,
26 10, 26 4, 31, 41 10, 31, 35, 41 10, 19, 31, 35, 41 10, 19, 31, 35, 36, 41 8, 19, 27, 29, 31, 33, 35, 41 19, 21, 24, 27, 29, 31, 33, 35, 36, 41 9, 19, 21, 24, 27, 29, 31, 33, 35, 36, 41 10, 19, 21, 24, 26, 27, 31, 33, 35, 36, 38, 39, 40, 41 5, 7, 9, 10, 13, 14, 18, 19, 21, 22, 23, 24, 26, 27, 29, 30, 31, 33, 34, 35, 36, 37, 38, 39, 40, 41
ARTICLE IN PRESS R.N. Gasimov et al. / European Journal of Operational Research xxx (2006) xxx–xxx
w1 = 15, w2 = 35 (see Table 10a), is ‘‘better’’ than the point (13661.42, 5) found by using weighted sum scalarization. This situation illustrates that the point (13661.42, 5) is actually a weak Pareto efficient point.
Fig. 3 demonstrates that the Pareto minimal points (78.87, 25) and (79.73, 24.25) calculated for different scalarization parameters (see Table 2a) are ‘‘behind’’ the straight line passing through the two Pareto minimal points (74.57, 29.13) and (82.71, 19.25), which means that they could not be calculated by using simple weighted scalarization approach. The computational results and solution times for 50-product models (P) and (P1) corresponding to different initial solutions are presented in Table 11. Note that the linear problem (P) could not be solved by using initial solution y2 = y36 = 0.9, while a solution to the nonlinear model (P1) is found in a shortest time by using the same initial solution and the same scalarization parameters. The computational results corresponding to different S values for problem (P2) are presented in Table 12.
Table 10a Additional Pareto minimal points found by solving 50–product problem (P), using conic scalarization for B1 = 79.73, B2 = 24.25 and different values of scalarization parameters a, w1 and w2 a
w1
w2
F1
F2
i: (yi = 1)
5 6 6 6 8 8 8 15 23
27 27 28 30 30 31 32 15 27
23 23 22 20 20 19 18 35 23
79.73 79.73 79.73 78.87 79.73 79.73 78.87 3133.302 63.554
24.25 24.25 24.25 25 24.25 24.25 25 5 187
5, 31, 41 5, 31, 42 5, 31, 43 1, 7, 10, 26 5, 31, 41 5, 31, 41 1, 7, 10, 26 1 4, 7, 10, 13, 14, 19, 21, 22, 23, 24, 26, 27, 29, 30, 31, 33, 35, 36, 37, 38, 39, 40, 41
Table 12 Computational results for 50-product problem (P2)
Table 10b Additional Pareto minimal points found by solving 50-product problem (P), using conic scalarization for B1 = 120, B2 = 9 a
w1
w2
F1
F2
i: (yi = 1)
1 2 3
5 4 3
45 46 47
92.18 106.05 120.5
13.13 12 11.38
1, 26 5, 13 1, 12
30
13
S
F1
i: yi = 1
Time (seconds)
1 2 3 4 5
166.909 91.027 79.731 73.811 70.684
4 2, 5, 5, 5,
80.3 473.89 1618.34 1191.75 671.64
26 31, 41 31, 35, 41 21, 31, 36, 41
(74.57, 29.13)
28 (78.87, 25)
26
(79.73, 24.25)
24 22 20 18 74
(82.71, 19.25) 75
76
77
78
79
80
81
82
83
84
Fig. 3. New Pareto minimal points calculated for 50-product test problem (P) found by using conic scalarization with B1 = 79.73, B2 = 24.25.
Table 11 Comparison of results for 50-product models (P) and (P1) corresponding to different initial solutions calculated for B1 = 500, B2 = 17 Model
Initial solution
a
w1
w2
F1
F2
i: (yi = 1)
Time (seconds)
P P P1
– y2 = y36 = 0.9 y2 = y36 = 0.9
7 7 7
31 31 31
19 19 19
78.87 – 78.87
25 – 25
1, 7, 10, 26 No solution was found 1, 7, 10, 26
6826.50 10.70
ARTICLE IN PRESS 14
R.N. Gasimov et al. / European Journal of Operational Research xxx (2006) xxx–xxx
Table 13 Computational results obtained using weighted sum scalarization, for 80-product linear problem (P) w1
w2
F1
F2
i: yi = 1
Time (seconds)
0 1–2 3–4 5–6 7 8 9–10 11 12–13 14–16 17–18 19–21 20–25 26 27–30 31 32–35 36–37 38–40 41 42 43–44 45–46 47–48
50 49–48 47–46 45–44 43 42 41–40 39 38–37 36–34 33–32 31–29 28–25 24 23–20 19 18–15 14–13 12–10 9 8 7–6 5–4 3–2
200956.7 1502.21 1388.92 1376.29 1332.41 1294.97 1253.99 1234.95 1205.37 1188.2 1177.07 1164.79 1148.11 1141.18 1130.27 1121.99 1117.38 1111.49 1107.79 1104.87 1102.71 1101.25 1098.99 1096.36
5 25.5 31 32.25 39.25 45.5 53.75 58.75 67.5 73.75 79 86.5 98.75 106.25 119 132.25 140.25 154.75 166 177.75 188.75 197.5 217 252
98.06 3737.68 3877.04 4635.57 5361 6578.69 4945.15 2335.48 2060.67 476.64 235.58 210.04 134.84 100.42 89.14 69.22 50 33.51 29.97 34.53 26.7 16.595 17.66 17.725
49
1
1096.11
261
50
0
1096.11
410
1 1, 9, 35 1, 3, 9, 35 1, 3, 8, 41 1, 3, 9, 14, 35 1, 3, 8, 34, 41 1, 3, 8, 14, 34, 41 1, 2, 5, 8, 11, 34, 41 1, 3, 8, 12, 34, 38, 41 1, 3, 4, 8, 14, 34, 38, 41 1, 2, 3, 4, 8, 14, 34, 38, 41 1, 2, 3, 4, 8, 11, 14, 34, 38, 41 1, 2, 3, 4, 8, 13, 19, 23, 34, 38, 41 1, 2, 3, 4, 8, 11, 13, 19, 23, 34, 38, 41 1, 2, 3, 4, 8, 11, 13, 20, 23, 31, 34, 38, 41 1, 2, 3, 4, 8, 11, 13, 19, 23, 31, 34, 35, 38, 41 1, 2, 4, 5, 8, 10, 11, 14, 19, 23, 31, 34, 35, 38, 41 1, 2, 4, 5, 8, 10, 11, 14, 19, 23, 31, 34, 35, 38, 39, 41 1, 2, 4, 5, 8, 10, 11, 14, 19, 23, 26, 31, 34, 35, 38, 39, 41 1, 2, 4, 5, 8, 10, 11, 12, 14, 19, 21, 23, 26, 31, 34, 35, 38, 39, 41 1, 2, 4, 5, 8, 10, 11, 14, 19, 21, 23, 26, 31, 32, 34, 35, 38, 39, 41 1, 2, 4, 5, 8, 10, 11, 14, 16, 19, 21, 23, 26, 31, 32, 34, 35, 38, 39, 41 1, 2, 3, 4, 5, 8, 10, 11, 14, 16, 19, 21, 23, 26, 31, 32, 34, 35, 37, 38, 39, 41 1, 2, 3, 4, 8, 10, 11, 12, 13, 14, 16, 19, 21, 23, 26, 30, 31, 32, 33, 34, 35, 37, 38, 39, 41 1, 2, 3, 4, 5, 8, 10, 11, 13, 14, 16, 19, 21, 23, 24, 26, 30, 31, 32, 34, 35, 37, 38, 39, 41 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 16, 17, 19, 20, 21, 23, 24, 26, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41
4.4. Computational results for 80-product problems In this section we present computational results for 80-product test problems. The computational results for the linear multi-objective model (P) obtained by the weighted sum scalarization approach are presented in Table 13. On the lines including solutions corresponding to more than one pair of weights, an average run time is given for each pair. As it can be seen from Table 13, in the situation when the only second objective will be minimized, i.e. when w1 = 0, w2 = 50 the only one roll has been chosen by the model (i = 1 for which yi = 1). In this situation the value of the first objective function related to the trim loss cost is very large, because all the efforts of the model are used to minimize the second objective function related to a total number of paper rolls decided to be used in the planning period. For the pairs of weights (1, 49) and (2, 48) the same optimal solution with F1 = 1502.21, F2 = 25.5 is obtained. In each solution correspond-
10.98 1.72
ing to these weights the 1st, 9th and 35th paper rolls are chosen (i = 1, 9, 35 for which yi = 1). It is remarkable that the optimal value of the first objective function related to the trim loss cost decreases with increasing its ‘‘weight’’ (the value of w1) in the total weighted sum whereas the number of paper rolls increases. Regarding the solution times, note that the most solution time (6578.69 seconds) is used for solving the scalarized problem with weights (8, 42), reported on the 6th line of the table. It is noticeable that the solution times for the problems preceding this line, steadily decrease as the weight of the first objective function increases. In any case Table 14 Additional Pareto efficient point found by solving 80-product linear problem (P), using conic scalarization for B1 = 1185, B2 = 75 a
w1
w2
F1
F2
i: (yi = 1)
Time (seconds)
15
16
34
1185.3
75.5
1, 3, 8, 11, 14, 34, 38, 41
6202.39
ARTICLE IN PRESS R.N. Gasimov et al. / European Journal of Operational Research xxx (2006) xxx–xxx
15
80 (1177,07; 79) 79 78 77 76 (1185,03; 75,5) 75 74 (1188,2; 73,75)
73 1175
1185
Fig. 4. New Pareto minimal points calculated for 80-product test problem (P) found by using conic scalarization with B1 = 1180, B2 = 75.
Table 15 Comparison of results for 80-product models (P) and (P1) corresponding to different initial solutions calculated for B1 = 1185, B2 = 75 by conic scalarization Model
Initial solution
a
w1
w2
F1
F2
i: (yi = 1)
Time (seconds)
P P1 P1
– y1 = y3 = 0.9, y8 = 0.2 y1 = y3 = y8 = y11 = y14 = y34 = y38 = y41 = 0.9
15 16 16
16 16 16
34 34 34
1185.03 2175.61 1185.03
75.50 17.25 75.50
1, 3, 8, 11, 14, 34, 38, 41 1, 3, 8 1, 3, 8, 11, 14, 34, 38, 41
6202.39 107.72 113.02
the solution time for the scalar problems obtained using weighted sum scalarization varies from 1.72 to 6578.69 seconds. Additional Pareto efficient point found for 80product linear problem (P), using conic scalarization approach is presented in Table 14. The scalarization parameters B1 = 1185 and B2 = 75 are selected between the Pareto efficient points (1188.2, 73.75) and (1177.07, 79) which correspond to the weights (16, 34) and (18, 32), respectively (see Table 13). It is noticeable that the new efficient solution using conic scalarization method has been found for the same weights. The corresponding geometrical interpretation is presented in Fig. 4. This figure demonstrates that the new efficient point (1185.3, 75.5) is behind the straight line joining points (1188.2, 73.75) and (1177.07, 79), and therefore is non-supported and cannot be calculated by the weighted sum scalarization method.
Table 16 Computational results for 80-product problem (P2) S
F1
i: yi = 1
Time (seconds)
1 2 3 4 5
3634.43 1912.57 1484.64 1366.29 1294.97
8 8, 3, 1, 1,
359.80 2228.20 4175.45 6591.63 8716.48
41 8, 41 6, 34, 41 3, 8, 34, 41
The computational results and solution times for 80-product models (P) and (P1) corresponding to different initial solutions are presented in Table 15. Note that an efficient solution (2175.61, 17.25) reported at the second line of this table is new. Results reported at second and third lines of Table 13 show that different efficient solutions can be obtained for the same scalarization parameters. The computational results for different S values for the problem (P2) are presented in Table 16. 5. Conclusions In this paper novel models and solution approach for a 1.5-dimensional multi-objective assortment problem are presented. This problem includes the determination of number of different widths of roll stocks to be maintained as inventory and the determination of how these roll stocks should be cut by choosing optimal cutting pattern combinations. A new multi-objective mixed integer linear programming model for this problem has been constructed in the form of simultaneously minimization two contradicting objectives related to the trim loss cost and the combined inventory cost in order to fulfill a given set of cutting orders. The same problem has equivalently been modeled by using nonlinear constraints. A particular case related to the situation when a producer is interested
ARTICLE IN PRESS 16
R.N. Gasimov et al. / European Journal of Operational Research xxx (2006) xxx–xxx
in choosing only a few number of types among all the possible roll sizes have also been studied. In all the developed models, binary variables are used only for identifying the paper rolls have to be chosen. Decision variables identifying the length of the paper which has to be cut have been expressed by using real variables. This situation significantly reduces a number of integer variables in all models, which has a great advantage from the solution process point of view. Besides, the model becomes more realistic with using two objective functions. A new method called a conic scalarization is proposed for scalarizing non-convex multi-objective problems and several experimental tests are reported in order to demonstrate the validity of the developed modeling and solving approaches. Since a single instance might be inconclusive about the quality of the solution approach, four test problems with 10, 30, 50 and 80 types of products and 41 different sizes of paper rolls have been generated and solved for each model. Cutting patterns being used in all models were generated by a computer program coded in Excel/Visual Basic Application. The entire test problems corresponding to (P) and (P1) are solved by firstly scalarizing them using both the weighted and conic scalarization approaches. It has been demonstrated that the conic scalarization approach enables one to calculate new Pareto efficient solutions corresponding to decision maker’s preferences, which cannot be calculated using simple weighted scalarization. The computation of new Pareto efficient points and solutions for the all test problems corresponding to both models (P) and (P1), demonstrates the quality and reliability of the approaches implemented. It has also been shown that the solution processes of problems corresponding to the nonlinear model (P1) are very sensitive to the chosen initial solutions and the solution times for such problems may be much shorter than those for linear problems when a suitable initial solution was chosen. The multi-objective programming and solving approaches developed in this paper can be used for studying the similar situations related to one, two and/or higher dimensional cutting and packing problems.
References Beasley, J.E., 2004. A population heuristic for constrained twodimensional non-guillotine cutting. European Journal of Operational Research 156, 601–627. Brooke, A., Kendrick, D., Meeraus, A., Raman R., 1998. GAMS A User’s Guide. GAMS Development Corporation. Downloadable from website: . Chankong, V., Haimes, Y.Y., 1983. Multiobjective Decision Making: Theory and Methodology. Elsevier Science Publishing, New York. Chauny, F., Loulou, R., Sadones, S., Soumis, F., 1987. A two-phase heuristic for strip packing: Algorithm and probabilistic analysis. Operational Research Letters 6 (1), 25–33. Cloud, F.H., 1994. Analysis of corrugator side trim. Tappi Journal 77 (4), 199–205. Dyckhoff, H., 1990. A typology of cutting and packing problems. European Journal of Operational Research 44, 145–159. Ehrgott, M., 2005. Multicriteria Optimization, second ed. Springer-Verlag. Gasimov, R.N., 2001. Characterization of the Benson proper efficiency and scalarization in nonconvex vector optimization. In: Koksalan, M., Zionts, S. (Eds.), Multiple Criteria Decision Making in the New Millennium, Lecture Notes in Economics and Mathematical Systems. Springer-Verlag, Berlin, Heidelberg, pp. 189–198. Geoffrion, A., 1968. Porper efficiency and the theory of vector maximization. Journal of Mathematical Analysis and Applications 22, 618–630. Holthaus, O., 2003. On the best number of different standard lengths to stock for one dimensional assortment problems. International Journal of Production Economics 83, 233– 246. Luc, D.T., 1989. Theory of Vector OptimizationLecture Notes in Economics and Mathematical Systems. Springer Verlag, Berlin. ¨ zdemir, M.S., Gasimov, R.N., 2004. The analytic hierarchy O process and multiobjective 0–1 faculty course assignment. European Journal of Operational Research 157 (2), 398– 408. ¨ zdemir, M.S., 2003. A genetic algorithm for 1.5 Sarac¸, T., O dimensional assortment problems with multiple objectives. Lecture Notes in Artificial Intelligence 2718, 41–51. Savsar, M., Cogun, C., 1994. Analysis and modeling of a production line in a corrugated box factory. International Journal of Production Research 32 (7), 1571–1589. Sweeney, P.E., Paternoster, E.R., 1992. Cutting and packing problems: A categorized, application-oriented research bibliography. Journal of Operational Research Society 43 (7), 691–706. Wa¨scher, G., Haußner, H., Schumann, H., 2005. An improved typology of cutting and packing problems. Working Paper No. 24, Last Revision: 2005-05-17, Otto von Guericke University, 38 p. Available from: .
