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

Integrated lot sizing in serial supply chains with production capacities

MANAGEMENT SCIENCE 2005年第11期51卷 1706-1719页

作者： van Hoesel, S Romeijn, HE Morales, DR Wagelmans, APM Maastricht Univ Fac Econ & Business Adm NL-6200 MD Maastricht Netherlands Univ Florida Dept Ind & Syst Engn Gainesville FL 32611 USA Univ Oxford Said Business Sch Oxford OX1 1HP England Erasmus Univ Inst Econometr NL-3000 DR Rotterdam Netherlands

We consider a model for a serial supply chain in which production, inventory, and transportation decisions are integrated in the presence of production capacities and concave cost functions. The model we study generalizes the uncapacitated serial single-item multilevel economic lot-sizing model by adding stationary production capacities at the manufacturer level. We present algorithms with a running time that is polynomial in the planning horizon when all cost functions are concave. In addition, we consider different transportation and inventory holding cost structures that yield improved running times: inventory holding cost functions that are linear and transportation cost functions that are either linear, or are concave with a fixed-charge structure. In the latter case, we make the additional common and reasonable assumption that the variable transportation and inventory costs are such that holding inventories at higher levels in the supply chain is more attractive from a variable cost perspective. While the running times of the algorithms are exponential in the number of levels in the supply chain in the general concave cost case, the running times are remarkably insensitive to the number of levels for the other two cost structures.

关键词： lot sizing integration of production planning and transportation dynamic programming polynomial time algorithms

来源：评论

学校读者我要写书评

暂无评论

Evaluation of Circuits Over Nilpotent and Polycyclic Groups

引用

ALGORITHMICA 2018年第5期80卷 1459-1492页

作者： Koenig, Daniel Lohrey, Markus Univ Siegen Siegen Germany

We study the circuit evaluation problem (also known as the compressed word problem) for finitely generated linear groups. The best upper bound for this problem is coRP (the complements of problems in randomized polynomial time), which is shown by a reduction to polynomial identity testing for arithmetic circuits. Conversely, the compressed word problem for the linear group is equivalent to polynomial identity testing. In the paper, we show that the compressed word problem for every finitely generated nilpotent group is in . Within the larger class of polycyclic groups we find examples where the compressed word problem is at least as hard as polynomial identity testing for skew arithmetic circuits. It is a major open problem, whether polynomial identity testing for skew arithmetic circuits can be solved in polynomial time.

关键词： NILPOTENT groups POLYCYCLIC groups polynomial time algorithms PI-algebras COMPUTATIONAL complexity

来源：评论

学校读者我要写书评

暂无评论

Induced star partition of graphs

引用

DISCRETE APPLIED MATHEMATICS 2022年 319卷 81-91页

作者： Shalu, M. A. Vijayakumar, S. Sandhya, T. P. Mondal, Joyashree Indian Inst Informat Technol Design & Mfg IIITDM Chennai 600127 India Univ Passau Dept Comp Sci & Math Passau Germany

Given a graph G, we call a partition (V-1, V-2, ... , V-k) of its vertex set an induced star partition of G if each set in the partition induces a star. In this paper, we consider the problem of finding an induced star partition of a graph of minimum size and its decision versions. This problem may be viewed as an amalgamation of the well-known dominating set and coloring problems. We obtain the following main results: (1) Deciding whether a graph can be partitioned into k induced stars is NP-complete for each fixed k >= 3 and has a polynomial time algorithm for each k <= 2. (2) It is NP-hard to approximate the minimum induced star partition size within n(1/2-epsilon )for all epsilon > 0. (3) The decision version of the induced star partition problem is NP-complete for subcubic bipartite planar graphs, line graphs (a subclass of K-1,K-r-free graphs, r >= 3), K-1,K-5-free split graphs and co-tripartite graphs. (4) The minimum induced star partition problem has an r/2 -approximation algorithm for K-1,K-r-free graphs (r >= 2) and a 2-approximation algorithms for split graphs. We also identify some fixed parameter tractable and exact exponential time algorithms that follow from the literature. (c) 2021 Elsevier B.V. All rights reserved.

关键词： Induced star partition polynomial time algorithms NP-completeness Approximation algorithms FPT Exact algorithms

来源：评论

学校读者我要写书评

暂无评论

The partial inverse minimum spanning tree problem when weight increase is forbidden

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2008年第2期188卷 348-353页

作者： Cai, Mao-Cheng Duin, C. W. Yang, Xiaoguang Zhang, Jianzhong Chinese Univ Hong Kong Dept Syst Engn & Engn Management Hong Kong Hong Kong Peoples R China Chinese Acad Sci Acad Math & Syst Sci Beijing 100080 Peoples R China Univ Amsterdam Fac Econ & Econometr Dept Operat Res NL-1012 WX Amsterdam Netherlands

In a partial inverse optimization problem there is an underlying optimization problem with a partially given solution. The objective is to find a minimal perturbation of some of the problem's parameter values, in such a way that the partial solution becomes a part of the optimal solution. We consider the partial inverse minimum spanning tree problem in an undirected weighted graph under the constraint that edge weights can not be increased: by decreasing one or more edge weights as little as possible, a given forest must be presented in the new minimum spanning tree. Under a quite general criterion function, evaluating the proposed decreases of weight, we show that this problem can be solved in polynomial time. (c) 2007 Elsevier B.V. All rights reserved.

关键词： partial inverse problem spanning tree weight reduction polynomial time algorithms

来源：评论

学校读者我要写书评

暂无评论

Approximate counting in SMT and value estimation for probabilistic programs

引用

ACTA INFORMATICA 2017年第8期54卷 729-764页

作者： Chistikov, Dmitry Dimitrova, Rayna Majumdar, Rupak Univ Warwick Dept Comp Sci Coventry W Midlands England Max Planck Inst Software Syst MPI SWS Kaiserslautern Germany Max Planck Inst Software Syst MPI SWS Saarbrucken Germany

#SMT, or model counting for logical theories, is a well-known hard problem that generalizes such tasks as counting the number of satisfying assignments to a Boolean formula and computing the volume of a polytope. In the realm of satisfiability modulo theories (SMT) there is a growing need for model counting solvers, coming from several application domains (quantitative information flow, static analysis of probabilistic programs). In this paper, we show a reduction from an approximate version of #SMT to SMT. We focus on the theories of integer arithmetic and linear real arithmetic. We propose model counting algorithms that provide approximate solutions with formal bounds on the approximation error. They run in polynomial time and make a polynomial number of queries to the SMT solver for the underlying theory, exploiting "for free" the sophisticated heuristics implemented within modern SMT solvers. We have implemented the algorithms and used them to solve the value problem for a model of loop-free probabilistic programs with nondeterminism.

关键词： COMPUTER software HEURISTIC algorithms polynomial time algorithms APPROXIMATION theory POLYTOPES PROBABILITY theory

来源：评论

学校读者我要写书评

暂无评论

An Exact Algorithm for Bilevel 0-1 Knapsack Problems

引用

MATHEMATICAL PROBLEMS IN ENGINEERING 2012年第1期2012卷 1-23页

作者： Mansi, Raid Alves, Claudio de Carvalho, J. M. Valerio Hanafi, Said Univ Minho Escola Engn Ctr Invest Algoritmi P-4710057 Braga Portugal Univ Minho Dept Prod & Sistemas P-4710057 Braga Portugal Univ Valenciennes & Hainaut Cambresis UMR 8530 LAMIH SIADE F-59313 Le Mt Houy 9 Valenciennes France

We propose a new exact method for solving bilevel 0-1 knapsack problems. A bilevel problem models a hierarchical decision process that involves two decision makers called the leader and the follower. In these processes, the leader takes his decision by considering explicitly the reaction of the follower. From an optimization standpoint, these are problems in which a subset of the variables must be the optimal solution of another (parametric) optimization problem. These problems have various applications in the field of transportation and revenue management, for example. Our approach relies on different components. We describe a polynomial time procedure to solve the linear relaxation of the bilevel 0-1 knapsack problem. Using the information provided by the solutions generated by this procedure, we compute a feasible solution (and hence a lower bound) for the problem. This bound is used together with an upper bound to reduce the size of the original problem. The optimal integer solution of the original problem is computed using dynamic programming. We report on computational experiments which are compared with the results achieved with other state-of-the-art approaches. The results attest the performance of our approach.

关键词： BILEVEL programming DECISION making REVENUE management TRANSPORTATION polynomial time algorithms

来源：评论

学校读者我要写书评

暂无评论

Stochastic Separated Continuous Conic Programming: Strong Duality and a Solution Method

引用

MATHEMATICAL PROBLEMS IN ENGINEERING 2014年第1期2014卷 1-20页

作者： Wang, Xiaoqing Sun Yat Sen Univ Lingnan Univ Coll Guangzhou 510275 Guangdong Peoples R China

We study a new class of optimization problems called stochastic separated continuous conic programming (SSCCP). SSCCP is an extension to the optimization model called separated continuous conic programming (SCCP) which has applications in robust optimization and sign-constrained linear-quadratic control. Based on the relationship among SSCCP, its dual, and their discretization counterparts, we develop a strong duality theory for the SSCCP. We also suggest a polynomial-time approximation algorithm that solves the SSCCP to any predefined accuracy.

关键词： DUALITY theory (Mathematics) ROBUST optimization LINEAR control systems DISCRETIZATION methods polynomial time algorithms STOCHASTIC analysis

来源：评论

学校读者我要写书评

暂无评论

Cyclic scheduling in a robotic production line

引用

JOURNAL OF SCHEDULING 2002年第1期5卷 23-41页

作者： Kats, V Levner, E Holon Inst Technol Dept Comp Sci IL-58102 Holon Israel Technion Israel Inst Technol Fac Ind Engn & Management IL-32000 Haifa Israel

The solution of cyclic scheduling problems is part of the classical repertoire on scheduling algorithms. We consider a problem of cyclic scheduling of identical parts in a production line where transportation of the parts between machines is performed by several robots. The problem is to find co-ordinated movements of the parts and robots in the line with the no-wait constraints imported;the objective is to maximize the throughput rate. Unlike many previous algorithms which are either heuristic or at best solve the single-robot version of the problem in O(m(4) log m) time, the proposed algorithm provides an exact solution for the more complicated case of multiple robots and solves the problem in O(m(3) log m) time, where in denotes the number of machines in the line. Copyright (C) 2002 John Wiley Sons, Ltd.

关键词： subject classification deterministic scheduling cyclic scheduling robotic scheduling polynomial time algorithms

来源：评论

学校读者我要写书评

暂无评论

Joint replenishment meets scheduling

引用

JOURNAL OF SCHEDULING 2023年第1期26卷 77-94页

作者： Gyorgyi, Peter Kis, Tamas Tamasi, timea Bekesi, Jozsef Inst Comp Sci & Control Eotvos Lorand Res Network Kende Str 13-17 H-1111 Budapest Hungary Eotvos Lorand Univ Inst Math Dept Operat Res Budapest Hungary Univ Szeged Fac Sci & Informat Dept Comp Algorithms & Artificial Intelligence Szeged Hungary

In this paper, we consider a combination of the joint replenishment problem (JRP) and single-machine scheduling with release dates. There is a single machine and one or more item types. Each job has a release date, a positive processing time, and it requires a subset of items. A job can be started at time t only if all the required item types were replenished between the release date of the job and time point t. The ordering of item types for distinct jobs can be combined. The objective is to minimize the total ordering cost plus a scheduling criterion, such as total weighted completion time or maximum flow time, where the cost of ordering a subset of items simultaneously is the sum of a joint ordering cost, and an additional item ordering cost for each item type in the subset. We provide several complexity results for the offline problem, and competitive analysis for online variants with min-sum and min-max criteria, respectively.

关键词： Joint replenishment Single-machine scheduling Complexity polynomial time algorithms Online algorithms

来源：评论

学校读者我要写书评

暂无评论

Due date assignments and scheduling a single machine with a general earliness/tardiness cost function

引用

COMPUTERS & OPERATIONS RESEARCH 2008年第5期35卷 1539-1545页

作者： Shabtay, Dvir Ben Gurion Univ Negev Dept Ind Engn & Management IL-84105 Beer Sheva Israel

We study three different due date assignment problems in scheduling a single machine which differ from each other based upon the objective function and due date assignment method being used. Two different objective functions are considered. The first is a cost function that includes earliness, tardiness and due date assignment penalties and the second is a function that includes penalties due to the number of tardy jobs and due date assignments. We assume that the earliness, tardiness and due date assignment penalties are continuous and non-decreasing functions of the corresponding duration. The goal is to minimize each objective function for two different due date assignment methods. The first is a method in which the assigned due dates are restricted to be equal while the second is a method that allows us to assign different due dates to different jobs. (c) 2006 Elsevier Ltd. All rights reserved.

关键词： single-machine scheduling due date assignment polynomial time algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：