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

Assembly line balancing under uncertainty: Robust optimization models and exact solution method

COMPUTERS & INDUSTRIAL ENGINEERING 2013年第2期65卷 261-267页

作者： Hazir, Oncu Dolgui, Alexandre TED Univ Iktisadi & Idari Bilimler Fak TR-06420 Ankara Turkey Ecole Natl Super Mines EMSE FAYOL CNRS UMR6158 LIMOS F-42023 St Etienne France

This research deals with line balancing under uncertainty and presents two robust optimization models. Interval uncertainty for operation times was assumed. The methods proposed generate line designs that are protected against this type of disruptions. A decomposition based algorithm was developed and combined with enhancement strategies to solve optimally large scale instances. The efficiency of this algorithm was tested and the experimental results were presented. The theoretical contribution of this paper lies in the novel models proposed and the decomposition based exact algorithm developed. Moreover, it is of practical interest since the production rate of the assembly lines designed with our algorithm will be more reliable as uncertainty is incorporated. Furthermore, this is a pioneering work on robust assembly line balancing and should serve as the basis for a decision support system on this subject. (c) 2013 Elsevier Ltd. All rights reserved.

关键词： Assembly line balancing Uncertainty Robust optimization Combinatorial optimization exact algorithms

来源：评论

学校读者我要写书评

暂无评论

Scheduling twin robots on a line

引用

NAVAL RESEARCH LOGISTICS 2014年第2期61卷 119-130页

作者： Erdogan, Guenes Battarra, Maria Laporte, Gilbert Univ Southampton Sch Management Southampton SO17 1BJ Hants England Univ Southampton Sch Math Southampton SO17 1BJ Hants England HEC Montreal Canada Res Chair Distribut Management Montreal PQ H3T 2A7 Canada

This article introduces the twin robots scheduling problem (TRSP), in which two robots positioned at the opposite ends of a rail are required to deliver items to positions along the rail, and the objective is to minimize the makespan. A proof of -hardness of the TRSP is presented, along with exact and heuristic algorithms. Computational results on challenging instances are *** (c) 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 119-130, 2014

关键词： robots Gantt chart scheduling exact algorithms approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Approximation algorithms for solving the line-capacitated minimum Steiner tree problem

引用

JOURNAL OF GLOBAL OPTIMIZATION 2022年第3期84卷 687-714页

作者： Li, Jianping Wang, Wencheng Lichen, Junran Liu, Suding Pan, Pengxiang Yunnan Univ Dept Math East Outer Ring South Rd Kunming 650504 Yunnan Peoples R China Chinese Acad Sci Acad Math & Syst Sci Inst Appl Math 55 Zhongguancun East Rd Beijing 100190 Peoples R China Beijing Univ Chem Technol Sch Math & Phys 15 North Third Ring East Rd Beijing 100029 Peoples R China

In this paper, we address the line-capacitated minimum Steiner tree problem (the Lc-MStT problem, for short), which is a variant of the (Euclidean) capacitated minimum Steiner tree problem and defined as follows. Given a set X = (r(1), r(2),...,r(n)} of n terminals in R-2, a demand function d : X -> N and a positive integer C, we are asked to determine the location of a line l and a Steiner tree T-l to interconnect these n terminals in X and at least one point located on this line l such that the total demand of terminals in each maximal subtree (of TO connected to the line l, where the terminals in such maximal subtree are all located at the same side of this line l, does not exceed the bound C. The objective is to minimize total weight Sigma(e is an element of Tl) w(e) of such a Steiner tree T-l among all line-capacitated Steiner trees mentioned-above, where weight w(e) = 0 if two endpoints of that edge e is an element of T-l are located on the line l and otherwise weight w(e) is the Euclidean distance between two endpoints of that edge e is an element of T-l . In addition, when this line l is as an input in R-2 and Sigma(r is an element of X) d(r) <= C holds, we refer to this version as the 1-line-fixed minimum Steiner tree problem (the 1Lf-MStT problem, for short). We obtain three main results. (1) Given a rho(st )-approximation algorithm to solve the Euclidean minimum Steiner tree problem and a rho(1Lf)-approximation algorithm to solve the 1Lf-MStT problem, respectively, we design a (rho(st)rho(1Lf )+2)-approximation algorithm to solve the Lc-MStT problem. (2) Whenever demand of each terminal r is an element of X is less than c/2, we provide a (rho(1Lf) + 2)-approximation algorithm to resolve the Lc-MStT problem. (3) Whenever demand of each terminal r is an element of X is at least c/2, using the Edmonds' algorithm to solve the minimum weight perfect matching as a subroutine, we present an exact algorithm in polynomial time to resolve the Lc-MStT problem.

关键词： Combinatorial optimization Locations of lines Line-capacitated Steiner trees Approximation algorithms exact algorithms

来源：评论

学校读者我要写书评

暂无评论

BOUNDING THE RUNNING TIME OF algorithms FOR SCHEDULING AND PACKING PROBLEMS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2016年第1期30卷 343-366页

作者： Jansen, K. Land, F. Land, K. Univ Kiel Inst Informat Olshausenstr 40 D-24098 Kiel Germany

Our goal is to show tight bounds on the running time of algorithms for scheduling and packing problems. To prove lower bounds, we investigate implications of the exponential time hypothesis on such algorithms. For exact algorithms we consider the dependence of the running time on the number n of items (for packing) or jobs (for scheduling). We prove a lower bound of 2(o(n)) x vertical bar vertical bar I vertical bar vertical bar(O(n)), where vertical bar vertical bar I vertical bar vertical bar denotes the encoding length of the instance, for several of these problems, including SUBSETSUM, KNAPSACK, BINPACKING, < P2 vertical bar vertical bar C-max >, and < P2 vertical bar vertical bar Sigma w(j)C(j)>. We also develop an algorithmic framework that is able to solve a large number of scheduling and packing problems in time 2o(n) x vertical bar vertical bar I vertical bar vertical bar(O(n)). Finally, we consider approximation schemes. We show that there is no polynomial time approximation scheme for MULTIPLEKNAPSACK (MKS) and 2D-KNAPSACK with running time 2(o(1/epsilon)) x vertical bar vertical bar I vertical bar vertical bar(O(n)) and n(o(1/epsilon)) x vertical bar vertical bar I vertical bar vertical bar(O(n)), respectively.

关键词： scheduling packing exponential time hypothesis exact algorithms lower bounds

来源：评论

学校读者我要写书评

暂无评论

Some Reduction Procedure for Computing Pathwidth of Undirected Graphs

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2015年第3期E98D卷 503-511页

作者： Ikeda, Masataka Nagamochi, Hiroshi Kyoto Univ Grad Sch Informat Dept Appl Math & Phys Kyoto 6068501 Japan

Computing an invariant of a graph such as treewidth and pathwidth is one of the fundamental problems in graph algorithms. In general, determining the pathwidth of a graph is NP-hard. In this paper, we propose several reduction methods for decreasing the instance size without changing the pathwidth, and implemented the methods together with an exact algorithm for computing pathwidth of graphs. Our experimental results show that the number of vertices in all chemical graphs in NCI database decreases by our reduction methods by 53.81% in average.

关键词： pathwidth exact algorithms graphs chemical graphs

来源：评论

学校读者我要写书评

暂无评论

algorithms for learning parsimonious context trees

引用

MACHINE LEARNING 2019年第6期108卷 879-911页

作者： Eggeling, Ralf Grosse, Ivo Koivisto, Mikko Univ Helsinki Dept Comp Sci Helsinki Finland Univ Tubingen Dept Comp Sci Tubingen Germany Martin Luther Univ Halle Wittenberg Inst Comp Sci Halle Germany

Parsimonious context trees, PCTs, provide a sparse parameterization of conditional probability distributions. They are particularly powerful for modeling context-specific independencies in sequential discrete data. Learning PCTs from data is computationally hard due to the combinatorial explosion of the space of model structures as the number of predictor variables grows. Under the score-and-search paradigm, the fastest algorithm for finding an optimal PCT, prior to the present work, is based on dynamic programming. While the algorithm can handle small instances fast, it becomes infeasible already when there are half a dozen four-state predictor variables. Here, we show that common scoring functions enable the use of new algorithmic ideas, which can significantly expedite the dynamic programming algorithm on typical data. Specifically, we introduce a memoization technique, which exploits regularities within the predictor variables by equating different contexts associated with the same data subset, and a bound-and-prune technique, which exploits regularities within the response variable by pruning parts of the search space based on score upper bounds. On real-world data from recent applications of PCTs within computational biology the ideas are shown to reduce the traversed search space and the computation time by several orders of magnitude in typical cases.

关键词： exact algorithms Structure learning Context-specific independence Branch and bound Sequential data

来源：评论

学校读者我要写书评

暂无评论

Order picking problems under weight, fragility and category constraints

引用

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 2017年第21期55卷 6361-6379页

作者： Chabot, Thomas Lahyani, Rahma Coelho, Leandro C. Renaud, Jacques Univ Laval CIRRELT Fac Sci Adm Quebec City PQ Canada Al Faisal Univ Coll Business Riyadh Saudi Arabia Inst Super Gest Ind LOGIQ Lab Sfax Tunisia Univ Laval Canada Res Chair Integrated Logist Quebec City PQ Canada

Warehouse order picking activities are among the ones that impact the most the bottom lines of warehouses. They are known to often account for more than half of the total warehousing costs. New practices and innovations generate new challenges for managers and open new research avenues. Many practical constraints arising in real-life have often been neglected in the scientific literature. We introduce, model and solve a rich order picking problem under weight, fragility and category constraints, motivated by our observation of a real-life application arising in the grocery retail industry. This difficult warehousing problem combines complex picking and routing decisions under the objective of minimising the distance travelled. We first provide a full description of the warehouse design which enables us to algebraically compute the distances between all pairs of products. We then propose two distinct mathematical models to formulate the problem. We develop five heuristic methods, including extensions of the classical largest gap, mid-point, S-shape and combined heuristics. The fifth one is an implementation of the powerful adaptive large neighbourhood search algorithm specifically designed for the problem at hand. We then implement a branch-and-cut algorithm and cutting planes to solve the two formulations. The performance of the proposed solution methods is assessed on a newly generated and realistic test bed containing up to 100 pickups and 7 aisles. We compare the bounds provided by the two formulations. Our in-depth analysis shows which formulation tends to perform better. Extensive computational experiments confirm the efficiency of the ALNS metaheuristic and derive some important insights for managing order picking in this kind of warehouses.

关键词： order picking warehousing formulations exact algorithms heuristics

来源：评论

学校读者我要写书评

暂无评论

The Complexity of Finding Effectors

引用

THEORY OF COMPUTING SYSTEMS 2017年第2期60卷 253-279页

作者： Bulteau, Laurent Fafianie, Stefan Froese, Vincent Niedermeier, Rolf Talmon, Nimrod Univ Paris Est Marne La Vallee CNRS UMR 8049 IGM LabInfo Marne La Vallee France Univ Bonn Inst Informat Bonn Germany Weizmann Inst Sci Rehovot Israel TU Berlin Inst Softwaretech & Theoret Informat Berlin Germany

The NP-hard Effectors problem on directed graphs is motivated by applications in network mining, particularly concerning the analysis of probabilistic information-propagation processes in social networks. In the corresponding model the arcs carry probabilities and there is a probabilistic diffusion process activating nodes by neighboring activated nodes with probabilities as specified by the arcs. The point is to explain a given network activation state as well as possible by using a minimum number of "effector nodes";these are selected before the activation process starts. We correct, complement, and extend previous work from the data mining community by a more thorough computational complexity analysis of Effectors, identifying both tractable and intractable cases. To this end, we also exploit a parameterization measuring the "degree of randomness" (the number of 'really' probabilistic arcs) which might prove useful for analyzing other probabilistic network diffusion problems as well.

关键词： Probabilistic information propagation Influence maximization etwork activation Social networks exact algorithms Parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Shortest color-spanning intervals

引用

THEORETICAL COMPUTER SCIENCE 2016年第Part3期609卷 561-568页

作者： Jiang, Minghui Wang, Haitao Utah State Univ Dept Comp Sci Logan UT 84322 USA

Given a set of n points on a line, where each point has one of k colors, and given an integer si >= 1 for each color i, 1 = 1. We also obtain some interesting results for the general problem SCSI-t. From the negati... 详细信息

Given a set of n points on a line, where each point has one of k colors, and given an integer si >= 1 for each color i, 1 <= i <= k, the problem SHORTEST COLOR-SPANNING t INTERVALS (SCSI-t) aims at finding t intervals to cover at least si points of each color i, such that the maximum length of the intervals is minimized. Chen and Misiolek introduced the problem SCSI-1, and presented an algorithm running in O(n) time if the input points are sorted. Khanteimouri et al. gave an O (n(2) logn) time algorithm for the special case of SCSI-2 with s(i) = 1 for all colors i. In this paper, we present an improved algorithm with running time of 0(n2) for SCSI-2 with arbitrary si >= 1. We also obtain some interesting results for the general problem SCSI-t. From the negative direction, we show that approximating SCSI-t within any ratio is NP-hard when t is part of the input, is W[2]-hard when t is the parameter, and is W[1]-hard with both t and k as parameters. Moreover, the NP-hardness and the W[2]-hardness with parameter t hold even if si = 1 for all i. From the positive direction, we show that SCSI-t with si = 1 for all i is fixed-parameter tractable with k as the parameter, and admits an exact algorithm running in 0 (2(k)n . max{k, logn}) time. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Color-spanning objects Computational geometry exact algorithms Parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

The production routing problem: A review of formulations and solution algorithms

引用

COMPUTERS & OPERATIONS RESEARCH 2015年 55卷 141-152页

作者： Adulyasak, Yossiri Cordeau, Jean-Francois Jans, Raf HEC Montreal Montreal PQ H3T 2A7 Canada CIRRELT Montreal PQ H3T 2A7 Canada

The production routing problem (PRP) combines the lot-sizing problem and the vehicle routing problem, two classical problems that have been extensively studied for more than half a century. The PRP is solved in an attempt to jointly optimize production, inventory, distribution and routing decisions and is thus a generalization of the inventory routing problem (IRP). Although the PRP has a complicated structure, there has been a growing interest in this problem during the past decade in both academia and industry. This article provides a comprehensive review of various solution techniques that have been proposed to solve the PRP. We attempt to provide an in-depth summary and discussion of different formulation schemes and of algorithmic and computational issues. Finally, we point out interesting research directions for further developments in production routing. (C) 2014 Elsevier Ltd. All rights reserved.

关键词： Integrated supply chain planning Production routing Inventory routing exact algorithms Heuristics Review

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：