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

One-operator, two-machine open shop and flow shop problems with setup times for machines and weighted number of tardy jobs objective

引用

OPTIMIZATION METHODS & SOFTWARE 2004年第2期19卷 165-178页

作者： Baki, MF Vickson, RG Univ Windsor Odette Sch Business Windsor ON N9B 3P4 Canada Univ Waterloo Dept Management Sci Waterloo ON N2L 3G1 Canada

One-operator two-machine open shop and flow shop problems are -hard in the ordinary sense even if all the weights are the same. We discuss two different pseudo polynomial dynamic programming recursions for each of the open shop and flow shop case. Some of the running times are better than those of the best known algorithms in the literature.

关键词： scheduling computational complexity pseudopolynomial algorithm one-operator two-machine

来源：评论

学校读者我要写书评

暂无评论

Timing analysis of asynchronous systems using time separation of events

引用

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS 1999年第8期18卷 1061-1076页

作者： Chakraborty, SA Yun, KY Dill, DL Fujitsu Labs Amer Inc Sunnyvale CA 94087 USA Univ Calif San Diego Dept Elect & Comp Engn La Jolla CA 92093 USA Stanford Univ Dept Comp Sci Palo Alto CA 94305 USA

This paper describes a pseudo-polynomial time algorithm for timing analysis of a class of choice-free asynchronous systems, called tightly coupled systems, with both min and max-type timing constraints and bounded component delays. The algorithm consists of two phases: I) long-term behavior analysis, that computes bounds on the time separation of events after the system has run for a sufficiently long period of time, and 2) startup behavior analysis, that computes time separations between events during an initial startup period after the system is powered up. The results of the analysis are conservative in the worst case;nevertheless, they are found to be exact in our experiments. To demonstrate the practical utility of the approach, an asynchronous differential equation solver chip has been modeled and analyzed using the proposed algorithm. We report results of datapath timing verification, intercontroller protocol timing verification and performance analysis of the chip using the proposed technique.

关键词： asynchronous logic circuits computer-aided analysis pseudopolynomial algorithm time separation timing analysis

来源：评论

学校读者我要写书评

暂无评论

The robust shortest path problem in series-parallel multidigraphs with interval data

引用

OPERATIONS RESEARCH LETTERS 2006年第1期34卷 69-76页

作者： Kasperski, A Zielinski, P Wroclaw Univ Technol Inst Ind Engn & Management PL-50370 Wroclaw Poland Wroclaw Univ Technol Inst Math PL-50370 Wroclaw Poland

In this paper the robust shortest path problem in edge series-parallel multidigraphs with interval costs is examined. The maximal regret criterion is applied to calculate the optimal solution. It is shown that this problem is NP-hard. A pseudopolynomial algorithm for the studied problem is constructed. (c) 2005 Elsevier B.V. All rights reserved.

关键词： robust optimization NP-hardness pseudopolynomial algorithm shortest path problem combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

Scheduling deteriorating jobs to minimize makespan

引用

NAVAL RESEARCH LOGISTICS 1998年第5期45卷 511-523页

作者： Kubiak, W van de Velde, S Mem Univ Newfoundland Fac Business Adm St Johns NF A1B 3X5 Canada Erasmus Univ Rotterdam Sch Management NL-3000 DR Rotterdam Netherlands

We consider a single-machine problem of scheduling n independent jobs to minimize makespan, in which the processing time of job J(j) grows by w(j) with each time unit its start is delayed beyond a given common critical date d. This processing time is p(j) if J(j) starts by d. We show that this problem is NP-hard, give a pseudopolynomial algorithm that runs in O(nd Sigma(j=1)(n) P-j) time and O(nd) space, and develop a branch-and-bound algorithm that solves instances with up to 100 jobs in a reasonable amount of time. We also introduce the case of bounded deterioration, where the processing time of a job grows no further if the job starts after a common maximum deterioration date D > d. For this case, we give two pseudopolynomial time algorithms: one runs in O(n(2)d(D - d) Sigma(j=1)(n) p(j)) time and O(nd(D - d)) space, the other runs in O(nd Sigma(j=1)(n) w(j)(Sigma(j=1)(n) p(j))(2)) time and O(nd Sigma(j=1)(n) w(j) Sigma(j=1)(n) p(j)) space. (C) 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 511-523, 1998.

关键词： single-machine scheduling deteriorating jobs NP-hardness dynamic programming pseudopolynomial algorithm branch and bound algorithm

来源：评论

学校读者我要写书评

暂无评论

SCHEDULING WITH MONOTONOUS EARLINESS AND TARDINESS PENALTIES

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 1993年第2期64卷 258-277页

作者： KAHLBACHER, HG UNIV KAISERSLAUTERN FACHBEREICH MATHW-6750 KAISERSLAUTERNGERMANY

We discuss the one-machine-model with deterministic processing times. In the first part we restrict the model to the common due date case. In the second part an equivalence between this model and the 'Equal Slack Due Date' model is shown. As a penalty function F we use the sum of identical functions f of the lateness (both earliness and tardiness). The function f must be monotonous with respect to the absolute lateness. No other restrictions are necessary. Several special cases are known in the literature and summarized here to show the generality of our approach. This idea of penalizing jobs whose completion times deviate from their due date arises in some scheduling models for 'just-in-time' production. We give two structural results for an optimal schedule: An optimal schedule works without idle times except eventually one at time 0 and is 'v-shaped'. Using these two structural results we construct an optimal schedule with a pseudopolynomial algorithm. This algorithm has a complexity bound of O(nP), where P denotes the sum of the given processing times. For a subclass of penalty functions, we extend the pseudopolynomial algorithm to a fully polynomial approximation scheme. The complexity bound for this approximation scheme is of the order O(n3 . (1/epsilon)), where epsilon denotes the relative precision of the approximate solution. As mentioned above we show the equivalence of the 'common due date' problem and the 'equal slack due date' problem. Mathematically these two problems can be expressed as: Common Due Date Rule: d(i):= d for all jobs i, and Equal Slack Rule: d(i):= d + p(i) for all jobs i, where p(i) denotes the given processing time of job i and d is a constant value.

关键词： SINGLE MACHINE SCHEDULING pseudopolynomial algorithm APPROXIMATION SCHEME

来源：评论

学校读者我要写书评

暂无评论

SCHEDULING AROUND A SMALL COMMON DUE DATE

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 1991年第2期55卷 237-242页

作者： HOOGEVEEN, JA VANDEVELDE, SL CTR MATH & COMP SCI 1009 AB AMSTERDAMNETHERLANDS

A set of n jobs has to be scheduled on a single machine which can handle only one job at a time. Each job requires a given positive uninterrupted processing time and has a positive weight. The problem is to find a schedule that minimizes the sum of weighted deviations of the job completion times from a given common due date d, which is smaller than the sum of the processing times. We prove that this problem is NP-hard even if all job weights are equal. In addition, we present a pseudopolynomial algorithm that requires O(n2d) time and O(nd) space.

关键词： SINGLE MACHINE SCHEDULING NP-HARDNESS pseudopolynomial algorithm

来源：评论

学校读者我要写书评

暂无评论

The equation A⊗x=B⊗y over (max, +)

引用

THEORETICAL COMPUTER SCIENCE 2003年第1期293卷 3-12页

作者： Cuninghame-Green, RA Butkovic, P Univ Birmingham Sch Math & Stat Birmingham B15 2TT W Midlands England

For the two-sided homogeneous linear equation system A circle times x = B circle times y over (max, +), with no infinite rows or columns in A or B, an algorithm is presented which converges to a finite solution from any finite starting point whenever a finite solution exists. If the finite elements of A, B are all integers, convergence is in a finite number of steps, for which a precise bound can be calculated if moreover one of A, B has only finite elements. The algorithm is thus pseudopolynomial in complexity. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： max-algebra linear system pseudopolynomial algorithm

来源：评论

学校读者我要写书评

暂无评论

A note on an optimal choice problem

引用

ZOR Zeitschrift für Operations Research Methods and Models of Operations Research 1993年第1期38卷 1-9页

作者： Kadelka, Dieter Institut für Mathematische Stochastik Universität Karlsruhe Karlsruhe 1 7500 Englerstr. 2 Germany

An item has probability p0 of not being workable. Before, going into use it has to be controlled by some deliberately chosen checks Ci which costs ci≥0,1≤i≤n. Total checking costs must be not larger than c0>0. I... 详细信息

An item has probability p₀ of not being workable. Before, going into use it has to be controlled by some deliberately chosen checks C_i which costs c_i≥0,1≤i≤n. Total checking costs must be not larger than c₀>0. It may happen that a check breaks a workable item, and failures may be overlooked. The problem is to determine an optimal sequence of checks subject to the cost constraints, such that the probability is maximized that an item leaving the checks is workable. In [1] this problem is solved by W. Stadje, but numerically the solution method only is applicable to problems of modest size. In this paper a simple reformulation of the original problem is presented. This first allows a simpler derivation of some of the results in [1]. Further, a dynamic programming algorithm is presented, which is pseudopolynomial, if costs c_i are integers. It then requires O(n·c₀) time. © 1993 Physica-Verlag.

关键词： dynamic programming Optimal choice problem pseudopolynomial algorithm

来源：评论

学校读者我要写书评

暂无评论

Network Design on Undirected Series-Parallel Graphs 8th

Network Design on Undirected Series-Parallel Graphs

引用

8th International Symposium on Combinatorial Optimization (ISCO)

作者： Bansal, Ishan Mao, Ryan Misra, Avhan Cornell Univ Ithaca NY 14850 USA

ISBN: (纸本)9783031609237;9783031609244

We study the single pair capacitated network design problem and the budget constrained max flow problem on undirected series-parallel graphs. These problems were well studied on directed seriesparallel graphs, but little is known in the context of undirected graphs. The major difference between the cases is that the source and sink of the problem instance do not necessarily coincide with the terminals of the underlying series-parallel graph in the undirected case, thus creating certain complications. We provide pseudopolynomial time algorithms to solve both of the problems and provide an FPTAS for the budget constrained max flow problem. We also provide some extensions, arguing important cases when the problems are polynomial-time solvable, and describing a series-parallel gadget that captures an edge upgrade version of the problems.

关键词： Network Design Series-Parallel Graphs pseudopolynomial algorithm Approximation Scheme

来源：评论

学校读者我要写书评

暂无评论

About One algorithm for Solving Scheduling Problem

引用

LOBACHEVSKII JOURNAL OF MATHEMATICS 2015年第2期36卷 211-214页

作者： Shulgina, O. N. Shcherbakova, N. K. Kazan Fed Univ Kremlevskaya ul 18 Kazan 420008 Russia

In this paper we proved the new properties optimal schedules for unknown strongly NPcomplete scheduling problem of minimizing maximum lateness on a single machine, not allowing preemption. pseudopolynomial implementat... 详细信息

关键词： scheduling lateness sequencing pseudopolynomial algorithm properties NP-completeness complexity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：