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

Computational analysis of a flexible assembly system design problem

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2000年第3期123卷 453-472页

作者： Kumar, A Jacobson, SH Sewell, EC So Illinois Univ Dept Math & Stat Edwardsville IL 62026 USA Grand Valley State Univ Seidman Sch Business Grand Rapids MI 49504 USA Univ Illinois Dept Mech & Ind Engn Urbana IL 61801 USA

Global competitive priorities are undergoing a marked shift from productivity and quality to flexibility and agility. This has resulted in a growing number of manufacturing companies realizing the importance of building customization capabilities into their production systems. Flexible assembly systems (FASs), consisting of a variety of processors such as assembly, inspection, packaging, and interactive operator consoles, provide a significant opportunity for improving product flexibility and, thereby, gaining sustainable competitive advantage. This paper formulates a decision problem for designing FASs and proves it to be NP-complete. A heuristic, called the pick and rule (PAR) heuristic, is presented to minimize the total number of processors, while determining the number of processors of each type, the sequence of the processors, and the operations to be performed at each processor. A lower bound for the minimum number of processor is derived, and used to assess the effectiveness of the PAR heuristic. An algorithm to compute this bound is also presented. An exact branch and bound algorithm is formulated to find optimal solutions and to provide guidance on the source of the gap between the PAR heuristic and the lower bound results. Computational results with the PAR heuristic, the lower bound algorithm, and the branch and bound algorithm are reported. (C) 2000 Elsevier Science B.V. All rights reserved.

关键词： heuristics lower bound algorithm computational analysis complexity branch and bound exact algorithm flexible manufacturing systems flexible assembly systems

来源：评论

学校读者我要写书评

暂无评论

An efficient algorithm for the single facility location problem with polyhedral norms and disk-shaped demand regions

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2017年第3期68卷 661-669页

作者： Berger, Andre Grigoriev, Alexander Winokurow, Andrej Maastricht Univ POB 616 NL-6200 MD Maastricht Netherlands

The single facility location problem with demand regions seeks for a facility locationminimizing the sum of the distances from n demand regions to the facility. The demand regions represent sales markets where the transportation costs are negligible. In this paper, we assume that all demand regions are disks of the same radius, and the distances are measured by a rectilinear norm, e.g. l(1) or l(infinity). We develop an exact combinatorial algorithm running in time O(n log(c) n) for some c dependent only on the space dimension. The algorithm is generalizable to the other polyhedral norms.

关键词： 1-median Single facility location problem Rectilinear norm Polyhedral norm exact algorithm

来源：评论

学校读者我要写书评

暂无评论

On nadir points of multiobjective integer programming problems

引用

JOURNAL OF GLOBAL OPTIMIZATION 2017年第3期69卷 699-712页

作者： Ozpeynirci, Ozgur Izmir Univ Econ Dept Logist Management Izmir Turkey

In this study, we consider the nadir points of multiobjective integer programming problems. We introduce new properties that restrict the possible locations of the nondominated points necessary for computing the nadir points. Based on these properties, we reduce the search space and propose an exact algorithm for finding the nadir point of multiobjective integer programming problems. We present an illustrative example on a three objective knapsack problem. We conduct computational experiments and compare the performances of two recent algorithms and the proposed algorithm.

关键词： Nadir point Multiobjective integer programming problem exact algorithm

来源：评论

学校读者我要写书评

暂无评论

On the weak computability of a four dimensional orthogonal packing and time scheduling problem

引用

THEORETICAL COMPUTER SCIENCE 2013年 501卷 1-10页

作者： Huang, Wenqi He, Kun Huazhong Univ Sci & Technol Sch Comp Sci & Technol Wuhan 430074 Peoples R China

This paper proposes a four dimensional orthogonal packing and time scheduling problem. The problem differs from the classical packing problems in that the position and orientation of each item in the container can be changed over time. In this way, the four dimensional space-time problem better uses the container time. Also, we consider a general case that all parameters are real numbers, which makes the problems more difficult to solve. This paper proposes an algorithm and proves that the algorithm could solve the problem optimally by a finite number of operations. We say this problem is weak computational, meaning that if there exists a universal machine that could represent real numbers and could do unit arithmetic or logical operation on real numbers in finite time, then the algorithm could find optimal solutions in finite time. This paper also presents a proof of the weak computability over a general case of the three dimensional orthogonal packing problem where all parameters are positive real numbers. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Computability exact algorithm Scheduling Higher dimensional packing Real parameters

来源：评论

学校读者我要写书评

暂无评论

An improved deterministic local search algorithm for 3-SAT

引用

THEORETICAL COMPUTER SCIENCE 2004年第1-3期329卷 303-313页

作者： Brueggemann, T Kern, W Univ Twente Fac Math Sci Dept Appl Math NL-7500 AE Enschede Netherlands

We slightly improve the pruning technique presented in Dantsin et al. (Theoret. Comput. Sci. 289 (2002) 69) to obtain an O*(1.473(n)) deterministic algorithm for 3-SAT. (C) 2004 Published by Elsevier B.V.

关键词： exact algorithm local search 3-SAT

来源：评论

学校读者我要写书评

暂无评论

Solving the Maximum Clique and Vertex Coloring Problems on Very Large Sparse Networks

引用

INFORMS JOURNAL ON COMPUTING 2015年第1期27卷 164-177页

作者： Verma, Anurag Buchanan, Austin Butenko, Sergiy Texas A&M Univ College Stn TX 77843 USA

This paper explores techniques for solving the maximum clique and vertex coloring problems on very largescale real-life networks. Because of the size of such networks and the intractability of the considered problems, previously developed exact algorithms may not be directly applicable. The proposed approaches aim to reduce the network instances to a size that is tractable for existing solvers, while preserving optimality. Two clique relaxation structures are exploited for this purpose. In addition to the known k -core structure, a newly introduced clique relaxation, k -community, is used to further reduce the instance size. Experimental results on real-life graphs (collaboration networks, P2P networks, social networks, etc.) show the proposed procedures to be effective by finding, for the first time, exact solutions for instances with over 18 million vertices.

关键词： maximum clique vertex coloring very-large-scale networks exact algorithm k-community k-core clique relaxation scale reduction

来源：评论

学校读者我要写书评

暂无评论

Labeled search trees and amortized analysis: Improved upper bounds for NP-hard problems

引用

algorithmICA 2005年第4期43卷 245-273页

作者： Chen, JN Kanj, IA Xia, G Texas A&M Univ Dept Comp Sci College Stn TX 77843 USA DePaul Univ Sch CTI Chicago IL 60604 USA

A sequence of exact algorithms to solve the VERTEX COVER and MAXIMUM INDEPENDENT SET problems have been proposed in the literature. All these algorithms appeal to a very conservative analysis that considers the size of the search tree, under a worst-case scenario, to derive an upper bound on the running time of the algorithm. In this paper we propose a different approach to analyze the size of the search tree. We use amortized analysis to show how simple algorithms, if analyzed properly, may perform much better than the upper bounds on their running time derived by considering only a worst-case scenario. This approach allows us to present a simple algorithm of running time O(1.194(k)k(2) + n) for the parameterized VERTEX COVER problem on degree-3 graphs, and a simple algorithm of running time O(1.1255 '') for the MAXIMUM INDEPENDENT SET problem on degree-3 graphs. Both algorithms improve the previous best algorithms for the problems.

关键词： vertex cover independent set exact algorithm parameterized algorithm

来源：评论

学校读者我要写书评

暂无评论

A DSATUR-based algorithm for the Equitable Coloring Problem

引用

COMPUTERS & OPERATIONS RESEARCH 2015年 57卷 41-50页

作者： Mendez-Diaz, Isabel Nasini, Graciela Severin, Daniel Univ Buenos Aires FCEyN Dept Ciencias Computac RA-2160 Buenos Aires DF Argentina Univ Nacl Rosario FCEIA RA-2000 Rosario Santa Fe Argentina Consejo Nacl Invest Cient & Tecn RA-1033 Buenos Aires DF Argentina

This paper describes a new exact algorithm for the Equitable Coloring Problem, a coloring problem where the sizes of two arbitrary color classes differ in at most one unit. Based on the well known DSATUR algorithm for the classic Coloring Problem, a pruning criterion arising from equity constraints is proposed and analyzed. The good performance of the algorithm is shown through computational experiments over random and benchmark instances. (C) 2014 Elsevier Ltd. All rights reserved.

关键词： Equitable coloring DSATUR exact algorithm

来源：评论

学校读者我要写书评

暂无评论

Using the idea of expanded core for the exact solution of bi-objective multi-dimensional knapsack problems

引用

JOURNAL OF GLOBAL OPTIMIZATION 2011年第4期49卷 589-606页

作者： Mavrotas, George Figueira, Jose Rui Antoniadis, Alexandros Natl Tech Univ Athens Athens 15780 Greece Inst Super Tecn Dept Engn & Gestao P-2780990 Porto Salvo Portugal

We propose a methodology for obtaining the exact Pareto set of Bi-Objective Multi-Dimensional Knapsack Problems, exploiting the concept of core expansion. The core concept is effectively used in single objective multi-dimensional knapsack problems and it is based on the "divide and conquer" principle. Namely, instead of solving one problem with n variables we solve several sub-problems with a fraction of n variables (core variables). In the multi-objective case, the general idea is that we start from an approximation of the Pareto set (produced with the Multi-Criteria Branch and Bound algorithm, using also the core concept) and we enrich this approximation iteratively. Every time an approximation is generated, we solve a series of appropriate single objective Integer Programming (IP) problems exploring the criterion space for possibly undiscovered, new Pareto Optimal Solutions (POS). If one or more new POS are found, we appropriately expand the already found cores and solve the new core problems. This process is repeated until no new POS are found from the IP problems. The paper includes an educational example and some experiments.

关键词： Knapsack problem Multi-objective programming Core exact algorithm

来源：评论

学校读者我要写书评

暂无评论

Optimal Solutions to a Real-World Integrated Airline Scheduling Problem

引用

TRANSPORTATION SCIENCE 2017年第1期51卷 250-268页

作者： Cacchiani, Valentina Salazar-Gonzalez, Juan-Jose Univ Bologna DEI I-40126 Bologna Italy Univ La Laguna DMEIO San Cristobal la Laguna 38271 Tenerife Spain

We study an integrated airline scheduling problem for a regional carrier. It integrates three stages of the planning process (i.e., fleet assignment, aircraft routing, and crew pairing) that are typically solved in sequence. Aircraft maintenance is also taken into account. The objective function aims at minimizing a weighted sum of the number of aircraft routes, the number of crew pairings, and the waiting times of crews between consecutive flights. In addition, it aims at maximizing the robustness of the solution by also minimizing the number of times that crews need to change aircraft. We present two mixed integer linear programming models for the integrated problem. The first formulation, called the path-path model, can be considered as the "natural model" in which both the crew pairings and the aircraft routes are represented by path-based variables. The other formulation, called the arc-path model, is a novel model in which the aircraft routes are represented by arc-based variables and the crew pairings by path-based variables. We propose two exact methods (called path-path method and arc-path method) for solving the integrated problem, each one based on one of the proposed models. Both methods consist of three phases. In the first phase, the linear programming relaxation of the corresponding model is solved to optimality by column generation on the path-based variables, thus providing a lower bound. The second phase computes a heuristic solution (upper bound) by using only the variables generated in the first phase. The third phase makes use of the lower and upper bounds (obtained in the previous phases) to compute an optimal solution. We propose a bounding cut based on computing a lower bound on the number of aircraft changes that are needed in a feasible solution, and empirically show that this cut significantly speeds up the exact methods. The proposed methods are tested on real-world instances of a regional carrier with up to 172 flights and three fleet op

关键词： integrated airline scheduling exact algorithm column generation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：