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

Machine scheduling with a rate-modifying activity

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2001年第1期128卷 119-128页

作者： Lee, CY Leon, VJ Texas A&M Univ Dept Ind Engn College Stn TX 77843 USA Texas A&M Univ Dept Engn Technol & Ind Distribut College Stn TX 77843 USA

Motivated by a problem commonly found in electronic assembly lines, this paper deals with the problem of scheduling jobs and a rate-modifying activity on a single machine. A rate-modifying activity is an activity that changes the production rate of the equipment under consideration. Hence the processing times of jobs vary depending on whether the job is scheduled before or after the rate-modifying activity. The decisions under consideration are when to schedule the rate-modifying activity and the sequence of jobs to optimize some performance measure. In this payer, we develop polynomial algorithms for solving problems of minimizing makespan, and total completion time respectively. We also develop pseudo-polynomial algorithms for solving problems of total weighted completion time under the agreeable ratio assumption. We prove that the problem of minimizing maximum lateness is NP-hard and also provide a pseudo-polynomial time algorithm to solve it optimally. (C) 2001 Elsevier Science B.V. All rights reserved.

关键词： machine scheduling job scheduling rate-modifying activity polynomial algorithms performance measure

来源：评论

学校读者我要写书评

暂无评论

Bidual Horn functions and extensions

引用

DISCRETE APPLIED MATHEMATICS 1999年 97卷 55-88页

作者： Eiter, T Ibaraki, T Makino, K Vienna Univ Technol Inst Ludwig Wittgenstein Labor Informat Syst A-1040 Vienna Austria Kyoto Univ Grad Sch Informat Dept Appl Math & Phys Kyoto 606 Japan Osaka Univ Grad Sch Engn Sci Dept Syst & Human Sci Toyonaka Osaka 560 Japan

Partially defined Boolean functions (pdBf) (T,F), where T,F subset of or equal to {0,1}(n) are disjoint sets of true and false vectors, generalize total Boolean functions by allowing that the function values on some input vectors are unknown. The main issue with pdBfs is the extension problem, which is deciding, given a pdBf, whether it is interpolated by a function f from a given class of total Boolean functions, and computing a formula for f. In this paper, we consider extensions of bidual Horn functions, which are the Boolean functions f such that both f and its dual function f(d) are Horn. They are intuitively appealing for considering extensions because they give a symmetric role to positive and negative information (i.e., true and false vectors) of a pdBf, which is not possible with arbitrary Horn functions. Bidual Horn functions turn out to constitute an intermediate class between positive and Horn functions which retains several benign properties of positive functions. Besides the extension problem, we study recognition of bidual Horn functions from Boolean formulas and properties of normal form expressions. We show that finding a bidual Horn extension and checking biduality of a Horn DNF is feasible in polynomial time, and that the latter is intractable from arbitrary formulas. We also give characterizations of shortest DNF expressions of a bidual Horn function f and show how to compute such an expression from a Horn DNF for f in polynomial time;for arbitrary Horn functions, this is NP-hard. Furthermore, we show that a polynomial total algorithm for dualizing a bidual Horn function exists if and only if there is such an algorithm for dualizing a positive function. (C) 1999 Elsevier Science B.V. All rights reserved.

关键词： Boolean functions Horn formulas satisfiability partially defined Boolean functions characteristic models polynomial algorithms

来源：评论

学校读者我要写书评

暂无评论

Minmax regret solutions for minimax optimization problems with uncertainty

引用

OPERATIONS RESEARCH LETTERS 2000年第2期27卷 57-65页

作者： Averbakh, I Western Washington Univ Dept Math Bellingham WA 98225 USA

We propose a general approach for finding minmax regret solutions for a class of combinatorial optimization problems with an objective function of minimax type and uncertain objective function coefficients. The approach is based on reducing a problem with uncertainty to a number of problems without uncertainty. The method is illustrated on bottleneck combinatorial optimization problems, minimax multifacility location problems and maximum weighted tardiness scheduling problems with uncertainty. (C) 2000 Published by Elsevier Science B.V. All rights reserved.

关键词： optimization under uncertainty polynomial algorithms minmax regret optimization

来源：评论

学校读者我要写书评

暂无评论

Minmax regret location-allocation problem on a network under uncertainty

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2007年第3期179卷 1025-1039页

作者： Conde, Eduardo Univ Seville Fac Matemat Dept Stat & Operat Res Seville 41012 Spain

We consider a robust location-allocation problem with uncertainty in demand coefficients. Specifically, for each demand point, only an interval estimate of its demand is known and we consider the problem of determining where to locate a new service when a given fraction of these demand points must be served by the utility. The optimal solution of this problem is determined by the "minimax regret" location, i.e., the point that minimizes the worst-case loss in the objective function that may occur because a decision is made without knowing which state of nature will take place. For the case where the demand points are vertices of a network we show that the robust location-allocation problem can be solved in O(min {p,n - p}n(3)m) time, where n is the number of demand points, p (p < n) is the fixed number of demand points that must be served by the new service and m is the number of edges of the network. (c) 2006 Elsevier B.V. All rights reserved.

关键词： location problems polynomial algorithms complexity robust optimization

来源：评论

学校读者我要写书评

暂无评论

Construction of the Jordan decomposition by means of Newton's method

引用

LINEAR ALGEBRA AND ITS APPLICATIONS 2000年第1-3期314卷 75-89页

作者： Schmidt, D Univ Essen Gesamthsch Fachbereich 6 D-45117 Essen Germany

Newton's method is applied to construct the semi-simple part of the Jordan decomposition of an algebraic element in an arbitrary algebra and to derive an efficient algorithm for its computation. Applications on th... 详细信息

关键词： polynomial algorithms normal forms of operators meromorphic differential operators

来源：评论

学校读者我要写书评

暂无评论

Parallel-machine scheduling of jobs with mixed job-, machine- and position-dependent processing times

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2022年第1期44卷 207-222页

作者： Przybylski, Bartlomiej Adam Mickiewicz Univ Fac Math & Comp Sci Uniwersytetu Poznanskiego 4 PL-61614 Poznan Poland

We consider a number of parallel-machine scheduling problems in which jobs have variable processing times. The actual processing time of each job is described by an arbitrary positive function of the position it holds on a machine. However, the function itself may additionally depend on the job or a machine this job was assigned to. Our aim is to find a schedule that minimizes the objectives of maximum completion time or the total completion time. We present a full set of polynomial solutions for the cases of jobs with no precedence constraints. We also show that the case of single-chained jobs may be not easier in general, but some polynomial results can be obtained, too.

关键词： Parallel-machine scheduling Variable processing times Position-dependent processing times Makespan Total completion time polynomial algorithms

来源：评论

学校读者我要写书评

暂无评论

Minimizing total completion time in a two-machine flowshop: Analysis of special cases

引用

MATHEMATICS OF OPERATIONS RESEARCH 1999年第4期24卷 887-910页

作者： Hoogeveen, JA Kawaguchi, T Univ Utrecht Dept Comp Sci NL-3584 CH Utrecht Netherlands Oita Univ Dept Comp Sci & Intelligent Syst Oita 87011 Japan

We consider the problem of minimizing total completion time in a two-machine flowshop. We present a heuristic with worst-case bound 2 beta/(alpha + beta), where alpha and beta denote the minimum and maximum processing time of all operations. Furthermore, we analyze four special cases: equal processing times on the first machine, equal processing times on the second machine, processing a job on the first machine takes time no less than its processing on the second machine, acid processing a job on the first machine takes time no more than its processing on the second machine. We prove that the first special case is NP-hard in the strong sense and present an O(n log n) approximation algorithm for it with worst-case bound 4/3. We repeat the easy polynomial algorithms for the cases two and three, and show that problem four is solvable in polynomial time as well.

关键词： flowshop total completion time NP-hardness heuristics worst-case analysis special case polynomial algorithms

来源：评论

学校读者我要写书评

暂无评论

Some Results on Stable Sets for k-Colorable P₆-Free Graphs and Generalizations

引用

DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE 2012年第2期14卷 37-56页

作者： Mosca, Raffaele Univ G DAnnunzio Dipartimento Econ I-65127 Pescara Italy

This article deals with the Maximum Weight Stable Set (MWS) problem (and some other related NP-hard problems) and the class of P-6-free graphs. The complexity status of MWS is open for P-6-free graphs and is open even for P-5-free graphs (as a long standing open problem). Several results are known for MWS on subclasses of P-5-free: in particular, MWS can be solved for k-colorable P-5-free graphs in polynomial time for every k (depending on k) and more generally for (P-5, K-p)-free graphs (depending on p), which is a useful result since for every graph G one can easily compute a k-coloring of G, with k not necessarily minimum. This article studies the MWS problem for k-colorable P-6-free graphs and more generally for (P-6, K-p)-free graphs. Though we were not able to define a polynomial time algorithm for this problem for every k, this article introduces: (i) some structure properties of P-6-free graphs with respect to stable sets, (ii) two reductions for MWS on (P-6;K-p)-free graphs for every p, (iii) three polynomial time algorithms to solve MWS respectively for 3-colorable P-6-free, for 4-colorable P-6-free, and for (P-6, K-4)-free graphs (the latter allows one to state, together with other known results, that MWS can be solved for (P-6, F)-free graphs in polynomial time where F is any four vertex graph).

关键词： Maximum Weight stable Set problem P6-free graphs polynomial algorithms

来源：评论

学校读者我要写书评

暂无评论

Stability routing with constrained path length for improved routability in dynamic MANETs

引用

PERSONAL AND UBIQUITOUS COMPUTING 2011年第8期15卷 799-810页

作者： Abid, Mohamed Amine Belghith, Abdelfettah Univ Manouba HANA Res Grp Manouba Tunisia

Quality of service (QoS) routing is known to be an NP-hard problem in case of two or more additive constraints, and several exact algorithms and heuristics have been proposed to address this issue. In this paper, we consider a particular two-constrained quality of service routing problem maximizing path stability with a limited path length in the quest of improving routability in dynamic multi-hop mobile wireless ad hoc networks. First, we propose a novel exact algorithm to solve the optimal weight-constrained path problem. We instantiate our algorithm to solve the most stable path not exceeding a certain number of hops, in polynomial time. This algorithm is then applied to the practical case of proactive routing in dynamic multi-hop wireless ad hoc networks. In these networks, an adequate compromise between route stability and its length in hops is essential for appropriately mitigating the impact of the network dynamics on the validity of established routes. Secondly, we set up a common framework for the comparison between three families of proactive routing: the shortest path-based routing, the most stable path-based routing and our proposed most stable constrained path routing. We show then through extensive simulations that routing based on our proposed algorithm selects appropriate stable paths yielding a very high routability with an average path length just above that of the shortest paths.

关键词： MANETS Constrained-based routing Quality of service routing Stability constraint NP-hard problems polynomial algorithms

来源：评论

学校读者我要写书评

暂无评论

An O(n⁴) Algorithm for the QAP Linearization Problem

引用

MATHEMATICS OF OPERATIONS RESEARCH 2011年第4期36卷 754-761页

作者： Kabadi, Santosh N. Punnen, Abraham P. Univ New Brunswick Fredericton NB Canada Simon Fraser Univ Surrey Dept Math Surrey BC V3T 0A3 Canada

An instance of the quadratic assignment problem (QAP) with cost matrix Q is said to be linearizable if there exists an instance of the linear assignment problem (LAP) with cost matrix C such that for each assignment, the QAP and LAP objective function values are identical. Several sufficiency conditions are known that guarantee linearizability of a QAP. However, no polynomial time algorithm is known to test if a given instance of QAP is linearizable. In this paper, we give a necessary and sufficient condition for an instance of a QAP to be linearizable and develop an O(n(4)) algorithm to solve the corresponding linearization problem, where n is the size of the QAP.

关键词： quadratic assignment problem linearization polynomial algorithms solvable cases

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：