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

A dual criteria sequencing problem with earliness and tardiness penalties

NAVAL RESEARCH LOGISTICS 2002年第4期49卷 422-431页

作者： Leung, JYT New Jersey Inst Technol Dept Comp Sci Newark NJ 07102 USA

We consider the problem of sequencing 71 jobs on a single machine. with each job having a processing time and a common due date. The common due date is assumed to be so large that all jobs can complete by the due date. It is known that there is an O(n log n)-time algorithm for finding a schedule with minimum total earliness and tardiness. In this article. we consider finding a schedule with dual criteria. The primary goal is to minimize the total earliness and tardiness. The secondary goals are to minimize: ( 1) the maximum earliness and tardiness' (2) the SLIM of the maximum of the squares of earliness and tardiness' (3) the sum of the squares of earliness and tardiness. For the first two criteria, we show that the problems are NP-hard and we give a fully polynomial time approximation scheme for both of them. For the last two criteria, we show that the ratio of the worst schedule versus the best schedule is no more than 3/2. (C) 2002 Wiley Periodicals, Inc.

关键词： single machine sequencing earliness tardiness NP-hardness fully polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

The coordination of transportation and batching scheduling

引用

APPLIED MATHEMATICAL MODELLING 2009年第10期33卷 3854-3862页

作者： Tang, Lixin Gong, Hua Northeastern Univ Logist Inst Liaoning Key Lab Mfg Syst & Logist Shenyang 110004 Peoples R China

We study a coordinated scheduling problem of production and transportation in which each job is transported to a single batching machine for further processing. There are m vehicles that transport jobs from the holding area to the batching machine. Each vehicle can transport only one job at a time. The batching machine can process a batch of jobs simultaneously where there is an upper limit on the batch size. Each batch to be processed occurs a processing cost. The problem is to find a joint schedule of production and transportation such that the sum of the total completion time and the total processing cost is optimized. For a special case of the problem where the job assignment to the vehicles is predetermined, we provide a polynomial time algorithm. For the general problem, we prove that it is NP-hard (in the ordinary sense) and present a pseudo-polynomial time algorithm. A fully polynomial time approximation scheme for the general problem is obtained by converting an especially designed pseudo-polynomial dynamic programming algorithm. Crown Copyright (C) 2009 Published by Elsevier Inc. All rights reserved.

关键词： Production scheduling Transportation Dynamic programming fully polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

approximation schemes for two-agent scheduling on parallel machines

引用

THEORETICAL COMPUTER SCIENCE 2013年 468卷 114-121页

作者： Zhao, Kejun Lu, Xiwen E China Univ Sci & Technol Sch Sci Dept Math Shanghai 200237 Peoples R China

Two models of two-agent scheduling problem on identical machines are considered in this paper. In both models, the goal is to minimize the makespan and the total completion time of agent A respectively, subject to an upper bound on the makespan of agent B. We prove that these two problems are NP-hard and can be solved in pseudo-polynomial time. Furthermore, we design the fully polynomial time approximation schemes for both problems, respectively. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Agent scheduling Parallel machines Algorithm Dynamic programming fully polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

Single machine batch scheduling to minimize the sum of total flow time and batch delivery cost with an unavailability interval

引用

INFORMATION SCIENCES 2014年 274卷 310-322页

作者： Yin, Yunqiang Ye, Deshi Zhang, Guochuan Zhejiang Univ Coll Comp Sci Hangzhou 310027 Zhejiang Peoples R China E China Inst Technol Coll Sci Nanchang 330013 Peoples R China

This paper addresses the problem of scheduling n nonresumable and simultaneously available jobs on a single machine, where the machine has a fixed unavailability interval, and the jobs are delivered in batches to the customers. There is no capacity limit on each delivery batch, and the cost per batch delivery is fixed and independent of the number of jobs in the batch. The goal is to find the optimal delivery date for each job and an optimal job sequence to minimize the sum of total flow time and batch delivery cost. The problem is shown to be NP-hard based on a reduction from the Equal-Size Partition Problem. Then a pseudo-polynomial time algorithm is developed, establishing that it is NP-hard in the ordinary sense. Finally, by applying the interval partitioning technique and the rounding technique, a fully polynomial time approximation scheme (FPTAS) and a bicriteria fully polynomial time approximation scheme are developed, which run in time O (n(5)/epsilon(2) + n(5) log n) and O (n(6)/epsilon), respectively. (C) 2014 Elsevier Inc. All rights reserved.

关键词： Scheduling Batch delivery fully polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

Penalty cost constrained identical parallel machine scheduling problem

引用

THEORETICAL COMPUTER SCIENCE 2015年第Part2期607卷 181-192页

作者： Li, Weidong Li, Jianping Zhang, Xuejie Chen, Zhibin Yunnan Univ Kunming 650091 Peoples R China Kunming Univ Sci & Technol Kunming 650500 Peoples R China

We consider a version of parallel machine scheduling with rejection. An instance of the problem is given by m identical parallel machines and a set of n independent jobs, with each job having a processing time and a penalty. A job may be accepted to be processed or be rejected at its penalty. The objective of the problem is to partition the set of jobs into two subsets, the subset of accepted and the subset of rejected jobs, and to schedule the set of accepted jobs such that the makespan is minimized under the constraint that the total penalty of the rejected jobs is no more than a given bound. In this paper, we present a 2-approximation algorithm within strongly polynomial time for the problem. We also present a polynomial time approximation scheme whose running time is O (nm(O(1/epsilon 2)) + mn(2)) for the problem. Moreover, for the case where the number of machines is a fixed constant m, our results lead to a fully polynomial time approximation scheme for the problem. Our result is fairly good in the sense that in a reasonable size of jobs, our FPTAS improves previous best running time from O(n(m+2)/epsilon(m)) to O(1/epsilon(2m+3) + mn(2)). (C) 2015 Elsevier B.V. All rights reserved.

关键词： Scheduling Rejection penalty approximation algorithms polynomial time approximation scheme fully polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

Characterizing achievable rates in multi-hop wireless mesh networks with orthogonal channels

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2005年第4期13卷 868-880页

作者： Kodialam, M Nandagopal, T Bell Labs Lucent Technol Holmdel NJ 07733 USA

This paper considers the problem of determining the achievable rates in multi-hop wireless mesh networks with orthogonal channels. We classify wireless networks with orthogonal channels into two types, half duplex and full duplex, and consider the problem of jointly routing the flows and scheduling transmissions to achieve a given rate vector. We develop tight necessary and sufficient conditions for the achievability of the rate vector. We develop efficient and easy to implement fully polynomial time approximation schemes for solving the routing problem. The scheduling problem is a solved as a graph edge-coloring problem. We show that this approach guarantees that the solution obtained is within 50% of the optimal solution in the worst case (within 67% of the optimal solution in a common special case) and, in practice, is close to 90% of the optimal solution on the average. The approach that we use is quite flexible and can be extended to handle more sophisticated interference conditions, and routing with diversity requirements.

关键词： Radio Networks Telecommunication Channels Telecommunication Network Routing Scheduling polynomial approximation Graph Colouring Radiofrequency Interference Diversity Reception Multihop Wireless Mesh Networks Orthogonal Channels Half Duplex Flow Routing Scheduling Transmission fully polynomial time approximation scheme Routing Problem Graph Edge Coloring Problem Interference Condition Diversity Requirement Intelligent Networks Spread Spectrum Communication Wireless Mesh Networks Routing Wireless Networks polynomials Interference Mobile Ad Hoc Networks Communication Channels Scheduling Algorithm

来源：评论

学校读者我要写书评

暂无评论

Performance evaluation of evolutionary class of algorithms - An application to 0-1 knapsack problem

引用

MATHEMATICAL AND COMPUTER MODELLING 1998年第7期27卷 57-72页

作者： Dutta, P DuttaMajumder, D Indian Stat Inst Elect & Commun Sci Unit Calcutta 700035 W Bengal India

The 0-1 knapsack [1] problem is a well-known NP-complete problem. There are different algorithms in the literature to attack this problem, two of them being of specific interest. One is a pseudo polynomial algorithm of order O(nK), K being the target of the problem. This algorithm works unsatisfactorily, as the given target becomes high. In fact, the complexity might become exponential in that case. The other scheme is a fully polynomial time approximation scheme (FPTAS) whose complexity is also polynomial time. The present paper suggests a probabilistic heuristic which is an evolutionary scheme accompanied by the necessary statistical formulation and its theoretical justification, We have identified parameters responsible for the performance of our evolutionary scheme which in turn would keep the option open for improving the scheme.

关键词： almost sure convergence stochastic process maximum likelihood estimates asymptotic joint distribution knapsack problem fully polynomial time approximation scheme pseudo polynomial algorithm

来源：评论

学校读者我要写书评

暂无评论

Optimal testing and repairing a failed series system

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2006年第3期12卷 279-295页

作者： Kovalyov, Mikhail Y. Portmann, Marie-Claude Oulamara, Ammar Ecole Mines Nancy MACSI Project LORIA INRIA F-540042 Nancy France Natl Acad Sci Belarus United Inst Informat Problems Minsk 220050 BELARUS Belarusian State Univ Fac Econ F-540042 Nancy France

We consider a series repairable system that includes n components and assume that it has just failed because exactly one of its components has failed. The failed component is unknown. Probability of each component to be responsible for the failure is given. Each component can be tested and repaired at given costs. Both testing and repairing operations are assumed to be perfect, that is, the result of testing a component is a true information that this component is failed or active (not failed), and the result of repairing is that the component becomes active. The problem is to find a sequence of testing and repairing operations over the components such that the system is always repaired and the total expected cost of testing and repairing the components is minimized. We show that this problem is equivalent to minimizing a quadratic pseudo-boolean function. polynomially solvable special cases of the latter problem are identified and a fully polynomial time approximation scheme (FPTAS) is derived for the general case. Computer experiments are provided to demonstrate high efficiency of the proposed FPTAS. In particular, it is able to find a solution with relative error epsilon = 0.1 for problems with more than 4000 components within 5 minutes on a standard PC with 1.2 Mhz processor.

关键词： test and repair policies failure diagnosis optimization pseudo-boolean functions fully polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

approximation scheme for restricted discrete gate sizing targeting delay minimization

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2011年第4期21卷 497-510页

作者： Liao, Chen Hu, Shiyan Michigan Technol Univ Dept Elect & Comp Engn Houghton MI 49931 USA

Discrete gate sizing is a critical optimization in VLSI circuit design. Given a set of available gate sizes, discrete gate sizing problem asks to assign a size to each gate such that the delay of a combinational circuit is minimized while the cost constraint is satisfied. It is one of the most studied problems in VLSI computer-aided design. Despite this, all of the existing techniques are heuristics with no performance guarantee. This limits the understanding of the discrete gate sizing problem in theory. This paper designs the first fully polynomial time approximation scheme (FPTAS) for the delay driven discrete gate sizing problem. The proposed approximation scheme involves a level based dynamic programming algorithm which handles the specific structures of a discrete gate sizing problem and adopts an efficient oracle query procedure. It can approximate the optimal gate sizing solution within a factor of (1+epsilon) in O(n (1+c) m (3c) /epsilon (c) ) time for 0 time for epsilon a parts per thousand yen1, where n is the number of gates, m is the maximum number of gate sizes for any gate, and c is the maximum number of gates per level. The FPTAS needs the assumption that c is a constant and thus it is an approximation algorithm for the restricted discrete gate sizing problem.

关键词： Combinatorial optimization VLSI design Delay optimization Discrete gate sizing fully polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

Improved approximation schemes for Early Work Scheduling on Identical Parallel Machines with a Common Due Date

引用

Journal of the Operations Research Society of China 2024年第2期12卷 341-350页

作者： Wei-Dong Li School of Mathematics and Statistics Yunnan UniversityKunming650504YunnanChina

We study the early work scheduling problem on identical parallel machines in order to maximize the total early work,i.e.,the parts of non-preemptive jobs that are executed before a common due *** preprocessing and constructing an auxiliary instance which has several good properties,for any desired accuracy,we propose an efficient polynomial time approximation scheme with running time O(f(1/ε)n),where n is the number of jobs and f(1/ε)is exponential in 1/ε,and a fully polynomial time approximation scheme with running time O(1/ε^(2m+1)+n)when the number of machines is fixed.

关键词： Scheduling Early work polynomial time approximation scheme Effcient polynomial time approximation scheme fully polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：