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

Lot sizing with capacity adjustment using on-site green and grid electricity

OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE 2025年 133卷

作者： Akbalik, Ayse Gicquel, Celine Penz, Bernard Rapine, Christophe Univ Lorraine Lab LCOMS 3 Rue Augustin Fresnel F-57073 Metz France Univ Paris Saclay Lab Interdisciplinaire Sci Numer LISN F-91190 Gif Sur Yvette France Univ Grenoble Alpes CNRS Grenoble INP G SCOP F-38000 Grenoble France

This paper investigates from a theoretical point of view how on-site generation of renewable energy can be incorporated in the optimization of a mid-term production and capacity planning problem. Specifically, we consider the generic case of a manufacturer using two energy sources to supply the electricity demand of its plant: an on-site renewable energy source and the electricity grid. The renewable energy source is considered to be free of use, but its available amount of energy fluctuates over time, whereas the grid power is virtually unlimited but incurs a cost per kWh purchased from the external provider. The objective is to satisfy a time- varying demand at a minimal cost over a mid-term horizon. The plant has a stationary nominal production capacity. To deal with the fluctuation of both the demand and the amount of energy supplied by the on-site source, the production capacity can be temporally increased by installing additional capacity, typically by changing the shift pattern or opening more production lines. Increasing the capacity allows to respond to peak demand and to build stock in periods where the energy is cheap but incurs a fixed cost. We study if an optimal solution of this integrated production, capacity, and energy planning problem can be computed efficiently to provide the best compromise. Our objective is to classify the complexity of the deterministic version of the problem. We establish its NP-hardness under mild assumptions and propose three polynomial time algorithms for special cases, according to the amount of energy provided by the renewable source. These algorithms rely on dominance structural properties which allow us to reduce the problem to well-studied lot-sizing problems with capacity or full batch delivery.

关键词： Energy-flexible production Lot-sizing problem Capacity planning Renewable energy polynomial time algorithm Complexity

来源：评论

学校读者我要写书评

暂无评论

The single item uncapacitated lot-sizing problem with time-dependent batch sizes: NP-hard and polynomial cases

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2013年第2期229卷 353-363页

作者： Akbalik, Ayse Rapine, Christophe Univ Lorraine Lab LGIPM F-57045 Metz France

This paper considers the uncapacitated lot sizing problem with batch delivery, focusing on the general case of time-dependent batch sizes. We study the complexity of the problem, depending on the other cost parameters, namely the setup cost, the fixed cost per batch, the unit procurement cost and the unit holding cost. We establish that if any one of the cost parameters is allowed to be time-dependent, the problem is NP-hard. On the contrary, if all the cost parameters are stationary, and assuming no unit holding cost, we show that the problem is polynomially solvable in time O(T-3), where T denotes the number of periods of the horizon. We also show that, in the case of divisible batch sizes, the problem with time varying setup costs, a stationary fixed cost per batch and no unit procurement nor holding cost can be solved in time O(T-3 logT). (C) 2013 Elsevier B.V. All rights reserved.

关键词： Inventory Uncapacitated lot sizing Batch delivery Stepwise cost polynomial time algorithm Complexity

来源：评论

学校读者我要写书评

暂无评论

Maximum Weight Independent Sets for (P₇,triangle)-free graphs in polynomial time

引用

DISCRETE APPLIED MATHEMATICS 2018年 236卷 57-65页

作者： Brandstaedt, Andreas Mosca, Raffaele Univ Rostock Inst Informat D-18051 Rostock Germany Univ G dAnnunzio Dipartimento Econ I-65121 Pescara Italy

The Maximum Weight Independent Set (MWIS) problem on finite undirected graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum weight sum. MWIS is one of the most investigated and most important algorithmic graph problems;it is well known to be NP-complete, and it remains NP-complete even under various strong restrictions such as for triangle-free graphs. For a long time, its complexity was an open problem for P-k-free graphs, k >= 5. Recently, Lokshtanov et al. (2014) proved that MWIS can be solved in polynomial time for P-5-free graphs, Lokshtanov et al. (2015) proved that MWIS can be solved in quasi polynomial time for P5-free graphs, and Bacso et al. (2016), and independently, Brause (2017) extended this to Pk-free graphs for every fixed k. Then very recently, Grzesik et al. (2017) showed that MWIS can be solved in polynomial time for P-6-free graphs. It still remains an open problem for Pk-free graphs, k >= 7. In this paper, we show that MWIS can be solved in polynomial time for (P-7,triangle)-free graphs. This extends the corresponding result for (P-6,triangle)-free graphs and may provide some progress in the study of MWIS for P-7-free graphs such as the recent result by Maffray and Pastor (2016) showing that MWIS can be solved in polynomial time for (P7,bull)-free graphs. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Graph algorithms Maximum Weight Independent Set problem P-7-free graphs Triangle-free graphs polynomial time algorithm Anti-neighborhood approach

来源：评论

学校读者我要写书评

暂无评论

polynomial time Learnability of Graph Pattern Languages Defined by Cographs

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2018年第3期E101D卷 582-592页

作者： Shoudai, Takayoshi Yoshimura, Yuta Suzuki, Yusuke Uchida, Tomoyuki Miyahara, Tetsuhiro Kyushu Int Univ Fac Contemporary Business Kitakyushu Fukuoka 8058512 Japan Kyushu Univ Dept Informat Fukuoka 8190395 Japan Hiroshima City Univ Fac Informat Sci Hiroshima 7313194 Japan Fujitsu Kyushu Syst Serv Ltd CAE Solut Dept Engn Solut Unit Fukuoka Japan

A cograph (complement reducible graph) is a graph which can be generated by disjoint union and complement operations on graphs, starting with a single vertex graph. Cographs arise in many areas of computer science and are studied extensively. With the goal of developing an effective data mining method for graph structured data, in this paper we introduce a graph pattern expression, called a cograph pattern, which is a special type of cograph having structured variables. Firstly, we show that a problem whether or not a given cograph pattern g matches a given cograph G is NP-complete. From this result, we consider the polynomial time learnability of cograph pattern languages defined by cograph patterns having variables labeled with mutually different labels, called linear cograph patterns. Secondly, we present a polynomial time matching algorithm for linear cograph patterns. Next, we give a polynomial time algorithm for obtaining a minimally generalized linear cograph pattern which explains given positive data. Finally, we show that the class of linear cograph pattern languages is polynomial time inductively inferable from positive data.

关键词： graph pattern matching cograph pattern polynomial time algorithm inductive inference computational learning theory

来源：评论

学校读者我要写书评

暂无评论

Optimal broadcast domination in polynomial time

引用

DISCRETE MATHEMATICS 2006年第24期306卷 3267-3280页

作者： Heggernes, Pinar Lokshtanov, Daniel Univ Bergen Dept Informat N-5020 Bergen Norway

Broadcast domination was introduced by Erwin in 2002, and it is a variant of the standard dominating set problem, such that different vertices can be assigned different domination powers. Broadcast domination assigns an integer power f (v) >= 0 to each vertex v of a given graph, such that every vertex of the graph is within distance f (v) from some vertex v having f (v)>= 1. The optimal broadcast domination problem seeks to minimize the sum of the powers assigned to the vertices of the graph. Since the presentation of this problem its computational complexity has been open, and the general belief has been that it might be NP-hard. In this paper, we show that optimal broadcast domination is actually in and we give a polynomial time algorithm for solving the problem on arbitrary graphs, using a non-standard approach. (c) 2006 Elsevier B.V. All rights reserved.

关键词： domination in graphs broadcast domination polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

3-Colouring AT-Free Graphs in polynomial time

引用

algorithmICA 2012年第3期64卷 384-399页

作者： Stacho, Juraj Wilfrid Laurier Univ Dept Phys & Comp Sci Waterloo ON N2L 3C5 Canada

Determining the complexity of the colouring problem on AT-free graphs is one of long-standing open problems in algorithmic graph theory. One of the reasons behind this is that AT-free graphs are not necessarily perfect unlike many popular subclasses of AT-free graphs such as interval graphs or co-comparability graphs. In this paper, we resolve the smallest open case of this problem, and present the first polynomial time algorithm for the 3-colouring problem on AT-free graphs.

关键词： Graph colouring Asteroidal triple AT-free Structural decomposition polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

Finding dominating induced matchings in S2,2,3-free graphs in polynomial time

引用

DISCRETE APPLIED MATHEMATICS 2020年 283卷 417-434页

作者： Brandstaedt, Andreas Mosca, Raffaele Univ Rostock Inst Informat A Einstein Str 22 D-18051 Rostock Germany Univ G DAnnunzio Dipartimento Econ I-65121 Pescara Italy

Let G = (V, E) be a finite undirected graph. An edge set E' subset of E is a dominating induced matching (d.i.m.) in G if every edge in E is intersected by exactly one edge of E'. The Dominating Induced Matching (DIM) problem asks for the existence of a d.i.m. in G;this problem is also known as the Efficient Edge Domination problem;it is the Efficient Domination problem for line graphs. The DIM problem is NP-complete even for very restricted graph classes such as planar bipartite graphs with maximum degree 3 and is solvable in linear time for P-7-free graphs, and in polynomial time for S-1,S-2,S-4-free graphs as well as for S-2,S-2,S-2-free graphs. In this paper, combining two distinct approaches, we solve it in polynomial time for S-2,S-2,S-3-free graphs. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Dominating induced matching Efficient edge domination S-2,S-2,S-3-free graphs polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

polynomial time Verification of Reachability in Sound Extended Free-Choice Workflow Nets

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2014年第2期E97A卷 468-475页

作者： Yamaguchi, Shingo Yamaguchi Univ Grad Sch Sci & Engn Ube Yamaguchi 7558611 Japan

Workflow nets are a standard way for modeling and analyzing workflows. There are two aspects in a workflow: definition and instance. In form of workflow nets, a workflow definition and a workflow instance are respectively represented as a net structure and a marking. The correctness of the workflow definition can be checked by using a workflow nets' property, called soundness. On the other hand, the correctness of the workflow instance can be checked by using a Petri nets' well-known property, called reachability. The reachability problem is known to be intractable. In this paper, we have shown that the reachability problem for (i) sound extended free-choice workflow nets with a marking representing one workflow instance or (ii) acyclic well-structured workflow nets with a marking representing one or more workflow instances can be solved in polynomial time.

关键词： Petri net workflow net reachability extended free-choice well-structured polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

polynomial time Inductive Inference of Languages of Ordered Term Tree Patterns with Height-Constrained Variables from Positive Data

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2017年第3期E100A卷 785-802页

作者： Shoudai, Takayoshi Aikoh, Kazuhide Suzuki, Yusuke Matsumoto, Satoshi Miyahara, Tetsuhiro Uchida, Tomoyuki Kyushu Int Univ Fac Int Studies Kitakyushu Fukuoka 8050062 Japan Kyushu Univ Dept Informat Fukuoka 8190395 Japan Hiroshima City Univ Fac Informat Sci Hiroshima 7313194 Japan Tokai Univ Fac Sci Hiratsuka Kanagawa 2591292 Japan Hitachi Ltd Res & Dev Grp Ctr Technol Innovat Informat & Telecommun Tokyo Tokyo Japan

An efficient means of learning tree-structural features from tree-structured data would enable us to construct effective mining methods for tree-structured data. Here, a pattern representing rich tree-structural features common to tree-structured data and a polynomial time algorithm for learning important tree patterns are necessary for mining knowledge from tree-structured data. As such a tree pattern, we introduce a term tree pattern t such that any edge label of t belongs to a finite alphabet Lambda, any internal vertex of t has ordered children and t has a new kind of structured variable, called a height-constrained variable. A height-constrained variable has a pair of integers (i, j) as constraints, and it can be replaced with a tree whose trunk length is at least i and whose height is at most j. This replacement is called height-constrained replacement. A sequence of consecutive height-constrained variables is called a variable-chain. In this paper, we present polynomial time algorithms for solving the membership problem and the minimal language (MINL) problem for term tree patterns having no variable-chain. The membership problem for term tree patterns is to decide whether or not a given tree can be obtained from a given term tree pattern by applying height-constrained replacements to all height-constrained variables in the term tree pattern. The MINL problem for term tree patterns is to find a term tree pattern t such that the language generated by t is minimal among languages, generated by term tree patterns, which contain all given tree-structured data. Finally, we show that the class, i.e., the set of all term tree patterns having no variable-chain, is polynomial time inductively inferable from positive data if vertical bar Lambda vertical bar >= 2.

关键词： tree structured pattern height-constrained variable polynomial time algorithm inductive inference computational learning theory

来源：评论

学校读者我要写书评

暂无评论

polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference

引用

THEORETICAL COMPUTER SCIENCE 2002年第1期289卷 503-516页

作者： Fleischner, H Kullmann, O Szeider, S Austrian Acad Sci Inst Discrete Math A-1010 Vienna Austria Univ Coll Swansea Dept Comp Sci Swansea SA2 8PP W Glam Wales

A formula (in conjunctive normal form) is said to be minimal unsatisfiable if it is unsatisfiable and deleting any clause makes it satisfiable. The deficiency of a formula is the difference of the number of clauses and the number of variables. It is known that every minimal unsatisfiable formula has positive deficiency. Until recently, polynomial-time algorithms were known to recognize minimal unsatisfiable formulas with deficiency 1 and 2. We state an algorithm which recognizes minimal unsatisfiable formulas with any fixed deficiency in polynomial time. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： minimal unsatisfiable SAT deficiency matching autarky polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：