检索结果-内蒙古大学图书馆

Three-dimensional bin packing problem with variable bin height

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2010年第2期202卷 347-355页

作者： Wu, Yong Li, Wenkai Goh, Mark de Souza, Robert Victoria Univ Inst Logist & Supply Chain Management Melbourne Vic 8001 Australia Natl Univ Singapore Logist Inst Asia Pacific Singapore 117574 Singapore Natl Univ Singapore NUS Business Sch Singapore 117592 Singapore

This paper studies a variant of the three-dimensional bin packing problem (3D-BPP), where the bin height can be adjusted to the cartons it packs. The bins and cartons to be packed are assumed rectangular in shape. The cartons are allowed to be rotated into any one of the six positions that keep the carton edges parallel to the bin edges. This greatly increases the difficulty of finding a good solution since the search space expands significantly comparing to the 3D-BPP where the cartons have fixed orientations. A mathematical (mixed integer programming) approach is modified based on [Chen, C. S., Lee, S. M., Shen, Q. S., 1995. An analytical model for the container loading problem. European journal of Operational Research 80 (1), 68-761 and numerical experiments indicate that the mathematical approach is not suitable for the variable bin height 3D-BPP. A special bin packing algorithm based on packing index is designed to utilize the special problem feature and is used as a building block for a genetic algorithm designed for the 3D-BPP. The paper also investigates the situation where more than one type of bin are used and provides a heuristic for packing a batch of cartons using the genetic algorithm. Numerical experiments show that our proposed method yields quick and satisfactory results when benchmarked against the actual packing practice and the MIP model with the latest version of CPLEX. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Bin packing mixed integer programming Optimization Genetic algorithms Batch bin packing Three-dimensional

来源：评论

学校读者我要写书评

暂无评论

Distribution systems design with role dependent objectives

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2010年第2期202卷 491-501页

作者： Kalcsics, Joerg Nickel, Stefan Puerto, Justo Rodriguez-Chia, Antonio M. Univ Karlsruhe TH Inst Operat Res D-76128 Karlsruhe Germany Univ Seville Dpto Estadist & Invest Operat E-41012 Seville Spain Univ Cadiz Pol Rio San Pedro Dpto Estadist & Invest Operat Puerto Real 11510 Spain

In this paper we introduce flexible models for capacitated discrete location problems. We describe three different points of view of a location problem in a logistics system. Different mathematical programming formulations are presented, illustrated by examples and compared using a battery of test problems. Extensive computational tests are done showing the potentials and limits of this kind of resolution approach. (C) 2009 Elsevier B.V. All rights reserved.

关键词： (B) Location mixed integer programming Strategic planning

来源：评论

学校读者我要写书评

暂无评论

Single vs. multiple objective supplier selection in a make to order environment

引用

OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE 2010年第3-4期38卷 203-212页

作者： Sawik, Tadeusz AGH Univ Sci & Technol Dept Operat Res & Informat Technol PL-30059 Krakow Poland

The problem of allocation of orders for custom parts among suppliers in make to order manufacturing is formulated as a single- or multi-objective mixed integer program. Given a set of customer orders for products, the decision maker needs to decide from which supplier to purchase custom parts required for each customer order. The selection of suppliers is based on price and quality of purchased parts and reliability of on time delivery. The risk of defective or unreliable supplies is controlled by the maximum number of delivery patterns (combinations of suppliers delivery dates) for which the average defect rate or late delivery rate can be unacceptable. Furthermore, the quantity or business volume discounts offered by the suppliers are considered. Numerical examples are presented and some computational results are reported. (C) 2009 Elsevier Ltd. All rights reserved.

关键词： Supplier selection Operational risk Discounts Multi-criteria decision making mixed integer programming

来源：评论

学校读者我要写书评

暂无评论

Optimization Based Production Planning With Hybrid Dynamics and Constraints

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2010年第12期55卷 2778-2792页

作者： Zhai, Qiaozhu Guan, Xiaohong Gao, Feng Xi An Jiao Tong Univ Syst Engn Inst MOE KLINNS Lab Xian 710049 Shaanxi Peoples R China Xi An Jiao Tong Univ SKLMSE Lab Xian 710049 Shaanxi Peoples R China Tsinghua Univ Ctr Intelligent & Networked Syst Beijing 100084 Peoples R China

Optimizing production planning has tremendous economic impact for many industrial production systems. In this paper, the planning problem of a class of production systems with hybrid dynamics and constraints is considered with practical background of power generation planning and other applications. The problem is solved within the Lagrangian relaxation framework, with the system wide demand and resource limit constraints relaxed by Lagrange multipliers. A new method is developed in this paper to obtain the exact optimal solutions to the subproblems with hybrid dynamics and constraints efficiently without discretizing the continuous production levels or introducing intermediate levels of relaxation. A novel definition of the discrete state associated with a consecutive time span is introduced so that solving each subproblem is converted into solving a number of continuous optimization problems and a discrete optimization problem separately. An efficient double dynamic programming (DP) method is developed to solve these subproblems and the principle of optimality is guaranteed for both the continuous and discrete problem. The production levels in a consecutive running span with non-convex piecewise linear cost functions are determined in a DP forward sweep without discretization. The DP method is then applied to determine the optimal discrete operating states across time efficiently. Numerical testing results demonstrate that the new method is efficient and effective for optimization based production planning with the complex hybrid dynamics and constraints.

关键词： Dynamic programming (DP) Lagrangian relaxation (LR) mixed integer programming production planning

来源：评论

学校读者我要写书评

暂无评论

On the extreme inequalities of infinite group problems

引用

MATHEMATICAL programming 2010年第1期121卷 145-170页

作者： Dey, Santanu S. Richard, Jean-Philippe P. Li, Yanjun Miller, Lisa A. Purdue Univ Sch Ind Engn W Lafayette IN 47907 USA Purdue Univ Krannert Sch Management W Lafayette IN 47907 USA Univ Minnesota Dept Mech Engn Minneapolis MN 55455 USA

Infinite group relaxations of integer programs (IP) were introduced by Gomory and Johnson (Math Program 3:23-85, 1972) to generate cutting planes for general IPs. These valid inequalities correspond to real-valued functions defined over an appropriate infinite group. Among all the valid inequalities of the infinite group relaxation, extreme inequalities are most important since they are the strongest cutting planes that can be obtained within the group-theoretic framework. However, very few properties of extreme inequalities of infinite group relaxations are known. In particular, it is not known if all extreme inequalities are continuous and what their relations are to extreme inequalities of finite group problems. In this paper, we describe new properties of extreme functions of infinite group problems. In particular, we study the behavior of the pointwise limit of a converging sequence of extreme functions as well as the relations between extreme functions of finite and infinite group problems. Using these results, we prove for the first time that a large class of discontinuous functions is extreme for infinite group problems. This class of extreme functions is the generalization of the functions given by Letchford and Lodi (Oper Res Lett 30(2):74-82, 2002), Dash and Gunluk (Proceedings 10th conference on integer programming and combinatorial optimization. Springer, Heidelberg, pp 33-45 (2004), Math Program 106:29-53, 2006) and Richard et al. (Math Program 2008, to appear). We also present several other new classes of discontinuous extreme functions. Surprisingly, we prove that the functions defining extreme inequalities for infinite group relaxations of mixed integer programs are continuous.

关键词： mixed integer programming Infinite group problem Extreme inequalities Extreme functions Cutting planes

来源：评论

学校读者我要写书评

暂无评论

Relations between facets of low- and high-dimensional group problems

引用

MATHEMATICAL programming 2010年第2期123卷 285-313页

作者： Dey, Santanu S. Richard, Jean-Philippe P. Purdue Univ Sch Ind Engn W Lafayette IN 47907 USA

One-dimensional infinite group problems have been extensively studied and have yielded strong cutting planes for mixed integer programs. Although numerical and theoretical studies suggest that group cuts can be significantly improved by considering higher-dimensional groups, there are no known facets for infinite group problems whose dimension is larger than two. In this paper, we introduce an operation that we call sequential-merge. We prove that the sequential-merge operator creates a very large family of facet-defining inequalities for high-dimensional infinite group problems using facet-defining inequalities of lower-dimensional group problems. Further, they exhibit two properties that reflect the benefits of using facets of high-dimensional group problems: they have continuous variables' coefficients that are not dominated by those of the constituent low-dimensional cuts and they can produce cutting planes that do not belong to the first split closure of MIPs. Further, we introduce a general scheme for generating valid inequalities for lower-dimensional group problems using valid inequalities of higher-dimensional group problems. We present conditions under which this construction generates facet-defining inequalities when applied to sequential-merge inequalities. We show that this procedure yields some two-step MIR inequalities of Dash and Gunluk.

关键词： mixed integer programming High-dimensional infinite group problem Facet-defining inequalities Cutting planes

来源：评论

学校读者我要写书评

暂无评论

mixed-integer sets from two rows of two adjacent simplex bases

引用

MATHEMATICAL programming 2010年第1-2期124卷 455-480页

作者： Andersen, Kent Louveaux, Quentin Weismantel, Robert Univ Liege Inst Montefiore B-4000 Liege Belgium Otto VonGuericke Univ Magdegurg Inst Math Optimierung D-39016 Magdeburg Germany

In Andersen et al. (Lecture Notes in Computer Science, vol. 4513, Springer, Berlin, pp. 1-15, 2007) we studied a mixed-integer set arising from two rows of a simplex tableau. We showed that facets of such a set can be obtained from lattice point free triangles and quadrilaterals associated with either three or four variables. In this paper we generalize our findings and show that, when upper bounds on the non-basic variables are also considered, further classes of facets arise that cannot be obtained from triangles and quadrilaterals. Specifically, when exactly one upper bound on a non-basic variable is introduced, stronger inequalities that can be derived from pentagons involving up to six variables also appear.

关键词： mixed integer programming Valid inequalities Two rows Lattice-point-free polyhedra

来源：评论

学校读者我要写书评

暂无评论

Improving benders decomposition using maximum feasible subsystem (MFS) cut generation strategy

引用

COMPUTERS & CHEMICAL ENGINEERING 2010年第8期34卷 1237-1245页

作者： Saharidis, Georgios K. D. Ierapetritou, Marianthi G. Rutgers State Univ Dept Chem & Biochem Engn Piscataway NJ 08854 USA Rutgers State Univ Ctr Adv Infrastructure & Transportat CAIT Piscataway NJ 08854 USA

A new multi-generation of cuts algorithm is presented in this paper to improve the efficiency of Benders decomposition approach for the cases that optimality cuts are difficult to be achieved within the iterations of the algorithm. This strategy is referred to as maximum feasible subsystem (MFS) cut generation strategy. In this approach in each iteration of the Benders algorithm an additional cut is generated that has the property to restrict the value of the objective function of the Benders master problem. To illustrate the efficiency of the proposed strategy, it is applied to a scheduling problem of multipurpose multiproduct batch plant. Two different partitioning alternatives are tested in order to show the importance of the way that a problem is decomposed upon the efficiency of the Benders algorithm. The application of the proposed acceleration procedure results in substantial reduction of CPU solution time and the total number of iterations in both decomposition alternatives. (C) 2009 Elsevier Ltd. All rights reserved.

关键词： Benders decomposition mixed integer programming Multi-generation of cuts Maximum feasible subsystem

来源：评论

学校读者我要写书评

暂无评论

Liveness-enforcing supervisors synthesis for a class of generalised Petri nets based on two-stage deadlock control and mathematical programming

引用

INTERNATIONAL JOURNAL OF CONTROL 2010年第10期83卷 2053-2066页

作者： Zhao, Mi Hou, Yifan Liu, Ding Shihezi Univ Machinery & Elect Coll Xinjiang 832003 Peoples R China Xidian Univ Sch Electromech Engn Xian 710071 Peoples R China

In this article we deal with deadlock prevention problems for S4PR, a class of generalised Petri nets, which can well model a large class of flexible manufacturing systems where deadlocks are caused by insufficiently marked siphons. We present a deadlock prevention methodology that is an iterative approach consisting of two stages. The first one is called siphon control, which is to add for each insufficiently marked minimal siphon a control place to the original net. Its objective is to prevent a minimal siphon from being insufficiently marked. The second one, called control-induced siphon control, is to add a control place to the augmented net with its output arcs connecting to the source transitions, which assures that there are no new insufficiently marked siphons generated. At each iteration, a mixed integer programming approach is adopted for generalised Petri nets to obtain an insufficiently marked minimal siphon from the maximal deadly siphon. This way complete siphon enumeration is avoided that is much more time-consuming for a sizeable plant model than the proposed method. The relation of the proposed method and the liveness and reversibility of the controlled net is obtained. Examples are presented to demonstrate the presented method.

关键词： Petri nets deadlock prevention mixed integer programming flexible manufacturing systems

来源：评论

学校读者我要写书评

暂无评论

Practical scheduling schemes with throughput guarantees for multi-hop wireless networks

引用

COMPUTER NETWORKS 2010年第5期54卷 766-780页

作者： Gupta, Gagan Raj Shroff, Ness B. Purdue Univ Sch Elect & Comp Engn W Lafayette IN 47907 USA Ohio State Univ Dept Elect & Comp Engn Columbus OH 43210 USA Ohio State Univ Dept Comp Sci & Engn Columbus OH 43210 USA

In wireless communication systems, the interference between links results in a challenging scheduling problem. A K-hop interference model is defined as one for which no two links within K-hops can successfully transmit at the same time (note that IEEE 802.11 DCF corresponds to a 2-hop interference model). For a given K, a throughput-optimal scheduler needs to solve a maximum weighted matching problem subject to the K-hop interference constraints. Previous work has mainly focused on developing scheduling algorithms with performance guarantees for the primary interference model (K = 1). For K >= 2, the problem is NP-Complete and cannot be approximated within a constant factor by any polynomial time algorithm. Our algorithm achieves at least a constant fraction (1/3) of the capacity region under any K-hop interference model. The simplicity of the solution and low control complexity makes it highly amenable for practical implementation. Simulation results show that when the communication overhead is taken into account, the delay characteristics of the proposed scheme may be better than the ideal optimal scheduler (given the prices at all the links, the ideal scheduler computes the optimal schedule instantaneously). (C) 2009 Elsevier B.V. All rights reserved.

关键词： Scheduling Stability Wireless networks K-hop interference Partition Throughput guarantee mixed integer programming

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：