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

approximation algorithms for the three-machine proportionate mixed shop scheduling

THEORETICAL COMPUTER SCIENCE 2020年 803卷 57-70页

作者： Liu, Longcheng Chen, Yong Dong, Jianming Goebel, Randy Lin, Guohui Luo, Yue Ni, Guanqun Su, Bing Xu, Yao Zhang, An Xiamen Univ Sch Math Sci Xiamen Peoples R China Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada Hangzhou Dianzi Univ Dept Math Hangzhou Peoples R China Zhejiang Sci Tech Univ Dept Math Hangzhou Peoples R China Fujian Agr & Forestry Univ Coll Management Fuzhou Peoples R China Xian Technol Univ Sch Econ & Management Xian Peoples R China

A mixed shop is a manufacturing infrastructure designed to process a mixture of a set of flow-shop jobs and a set of open-shop jobs. Mixed shops are in general much more complex to schedule than flow-shops and open-shops, and have been studied since the 1980's. We consider the three machine proportionate mixed shop problem denoted as M3 vertical bar prpt vertical bar C-max, in which by "proportionate" each job has equal processing times on all three machines. Koulamas and Kyparisis (2015) [6] showed that the problem is solvable in polynomial time in some very special cases;for the non-solvable case, they proposed a 5/3-approximation algorithm. In this paper, we first present an improved 4/3-approximation algorithm and show that this ratio of 4/3 is asymptotically tight;when the largest job is a flow-shop job, we then present a fully polynomial-time approximation scheme (FPTAS). On the negative side, while the F3 vertical bar prpt vertical bar C-max problem is polynomialtime solvable, we show an interesting hardness result that adding one open-shop job to the job set makes the problem NP-hard if this open-shop job is larger than any flow-shop job. We are able to design an FPTAS for this special case too. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Scheduling Mixed shop Proportionate approximation algorithm fully polynomial-time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

A Dynamic Programming Approach for the Decentralized Control of Discrete Optimizers with Quadratic Utilities and Shared Constraint 28

A Dynamic Programming Approach for the Decentralized Control...

引用

28th Mediterranean Conference on Control and Automation (MED)

作者： Carli, Raffaele Dotoli, Mariagrazia Polytech Bari Dept Elect & Informat Engn Bari Italy

ISBN: (纸本)9781728157429

This paper addresses the problem of controlling a large set of agents, each with a quadratic utility function depending on individual combinatorial choices, and all sharing an affine constraint on available resources. Such a problem is formulated as an integer mono-constrained bounded quadratic knapsack problem. Differently from the centralized approaches typically proposed in the related literature, we present a new decentralized algorithm to solve the problem approximately in polynomial time by decomposing it into a finite series of sub-problems. We assume a minimal communication structure through the presence of a central coordinator that ensures the information exchange between agents. The proposed solution relies on a decentralized control algorithm that combines discrete dynamic programming with additive decomposition and value functions approximation. The optimality and complexity of the presented strategy are discussed, highlighting that the algorithm constitutes a fully polynomial approximation scheme. Numerical experiments are presented to show the effectiveness of the approach in the optimal resolution of largescale instances.

关键词： decentralized optimization knapsack problem dynamic programming fully polynomial-time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

TOWARD BREAKING THE CURSE OF DIMENSIONALITY: AN FPTAS FOR STOCHASTIC DYNAMIC PROGRAMS WITH MULTIDIMENSIONAL ACTIONS AND SCALAR STATES

引用

SIAM JOURNAL ON OPTIMIZATION 2019年第2期29卷 1131-1163页

作者： Halman, Nir Nannicini, Giacomo Hebrew Univ Jerusalem Jerusalem Sch Business Adm IL-91905 Mt Scopus Israel IBM Corp TJ Watson Res Ctr 1101 Kitchawan Rd Yorktown Hts NY 10598 USA

We propose a fully polynomial-time approximation scheme (FPTAS) for stochastic dynamic programs with multidimensional action, scalar state, convex costs, and linear state transition function. The action spaces are polyhedral and described by parametric linear programs. This type of problem finds applications in the area of optimal planning under uncertainty, and can be thought of as the problem of optimally managing a single nondiscrete resource over a finite time horizon. We show that under a value oracle model for the cost functions this result for one-dimensional state space is the "best possible," because a similar dynamic programming model with two-dimensional state space does not admit a polynomial-time approximation scheme. The FPTAS relies on the solution of polynomial-sized linear programs to recursively compute an approximation of the value function at each stage. Our paper enlarges the class of dynamic programs that admit an FPTAS by showing, under suitable conditions, how to deal with multidimensional action spaces and with vectors of continuous random variables with bounded support. These results bring us one step closer to overcoming the curse of dimensionality of dynamic programming.

关键词： dynamic programming approximation algorithms fully polynomial-time approximation scheme multistage linear programming

来源：评论

学校读者我要写书评

暂无评论

Load Balancing for Interdependent IoT Microservices

Load Balancing for Interdependent IoT Microservices

引用

IEEE Conference on Computer Communications (IEEE INFOCOM)

作者： Yu, Ruozhou Kilari, Vishnu Teja Xue, Guoliang Yang, Dejun Arizona State Univ Tempe AZ 85287 USA Colorado Sch Mines Golden CO 80401 USA

ISBN: (纸本)9781728105154

Advances in virtualization technologies and edge computing have inspired a new paradigm for Internet-of-Things (IoT) application development. By breaking a monolithic application into loosely coupled microservices, great gain can be achieved in performance, flexibility and robustness. In this paper, we study the important problem of load balancing across IoT microservice instances. A key difficulty in this problem is the interdependencies among microservices: the load on a successor microservice instance directly depends on the load distributed from its predecessor microservice instances. We propose a graph-based model for describing the load dependencies among microservices. Based on the model, we first propose a basic formulation for load balancing, which can be solved optimally in polynomial time. The basic model neglects the quality-of-service (QoS) of the IoT application. We then propose a QoS-aware load balancing model, based on a novel abstraction that captures a realization of the application's internal logic. The QoS-aware load balancing problem is NP-hard. We propose a fully polynomial-time approximation scheme for the QoS-aware problem. We show through simulation experiments that our proposed algorithm achieves enhanced QoS compared to heuristic solutions.

关键词： IoT microservice application graph load balancing fully polynomial-time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

Single-machine scheduling and common due date assignment with potential machine disruption

引用

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 2018年第3期56卷 1345-1360页

作者： Xiong, Xiaoyun Wang, Dujuan Cheng, T. C. Edwin Wu, Chin-Chia Yin, Yunqiang Kunming Univ Sci & Technol Fac Sci Kunming Yunnan Peoples R China Dalian Univ Technol Sch Management Sci & Engn Dalian Peoples R China Dalian Maritime Univ Transportat Management Coll Dalian Peoples R China Hong Kong Polytech Univ Dept Logist & Maritime Studies Kowloon Hong Kong Peoples R China Feng Chia Univ Dept Stat Taichung Taiwan

This paper studies a single-machine due date assignment and scheduling problem in a disruptive environment, where a machine disruption may occur at a particular time that will last for a period of time with a certain probability, and the job due dates are determined by the decision-maker using the popular common due date assignment method. The goal is to determine jointly the optimal job sequence and the common due date so as to minimise the expected value of an integrated cost function that includes the earliness, tardiness and due date assignment costs. We analyse the computational complexity status of various cases of the problem, and develop pseudo-polynomial-time solution algorithms, randomised adaptive search algorithms, and fully polynomial-time approximation schemes for them, if viable. Finally, we conduct extensive numerical testing to assess the performance of the proposed algorithms.

关键词： scheduling dynamic programming disruption management due date assignment fully polynomial-time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

Parallel-machine scheduling of deteriorating jobs with potential machine disruptions

引用

OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE 2017年 69卷 17-28页

作者： Yin, Yunqiang Wang, Yan Cheng, T. C. E. Liu, Wenqi Li, Jinhai Kunming Univ Sci & Technol Fac Sci Kunming Peoples R China Hong Kong Polytech Univ Dept Logist & Maritime Studies Kowloon Hong Kong Peoples R China

We consider parallel-machine scheduling of deteriorating jobs in a disruptive environment in which some of the machifies will become unavailable due to potential disruptions. This means that a disruption to some of the machines may occur at a particular time, which will last for a period of time with a certain probability. If a job is disrupted during processing by a disrupted machine and it does not need (needs) to re-start after the machine becomes available again, it is called the resumable (non-resumable) case. By deteriorating jobs, we mean that the actual processing time of a job grows when it is scheduled for processing later because the machine efficiency deteriorates over time due to machine usage and aging. However, a repaired machine will return to its original state of efficiency. We consider two cases, namely performing maintenance immediately on the disrupted machine when a disruption occurs and not performing machine maintenance. In each case, the objective is to determine the optimal schedule to minimize the expected total completion time of the jobs in both non-resumable and resumable cases. We determine the computational complexity status of various cases of the problem, and provide pseudo polynomial-time solution algorithms and fully polynomial-time approximation schemes for them, if viable. (C) 2016 Elsevier Ltd. All rights reserved.

关键词： Scheduling Deteriorating jobs Disruptive environment fully polynomial-time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

An FPTAS for the parallel two-stage flowshop problem

引用

Theoretical Computer Science 2017年 657卷 64-72页

作者： Jianming Dong Weitian Tong Taibo Luo Xueshi Wang Jueliang Hu Yinfeng Xu Guohui Lin Department of Mathematics Zhejiang Sci-Tech University Hangzhou Zhejiang 310018 China Department of Computing Science University of Alberta Edmonton Alberta T6G 2E8 Canada Department of Computer Sciences Georgia Southern University Statesboro GA 30458 USA Business School Sichuan University Chengdu Sichuan 610065 China State Key Lab for Manufacturing Systems Engineering Xi'an Shaanxi 710049 China

We consider the NP-hard m - parallel two-stage flowshop problem, abbreviated as the ( m , 2 ) -PFS problem, where we need to schedule n jobs to m parallel identical two-stage flowshops in order to minimize the makespan, i.e. the maximum completion time of all the jobs on the m flowshops. The ( m , 2 ) -PFS problem can be decomposed into two subproblems: to assign the n jobs to the m parallel flowshops, and for each flowshop to schedule the jobs assigned to the flowshop. We first present a pseudo-polynomial time dynamic programming algorithm to solve the ( m , 2 ) -PFS problem optimally, for any fixed m , based on an earlier idea for solving the ( 2 , 2 ) -PFS problem. Using the dynamic programming algorithm as a subroutine, we design a fully polynomial-time approximation scheme (FPTAS) for the ( m , 2 ) -PFS problem.

关键词： Two-stage flowshop scheduling Multiprocessor scheduling Makespan Dynamic programming fully polynomial-time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

approximation schemes for Single-Machine Scheduling with a Fixed Maintenance Activity to Minimize the Total Amount of Late Work

引用

NAVAL RESEARCH LOGISTICS 2016年第2期63卷 172-183页

作者： Yin, Yunqiang Xu, Jianyou Cheng, T. C. E. Edwin Wu, Chin-Chia Wang, Du-Juan Kunming Univ Sci & Technol Dept Math Kunming 650093 Peoples R China Northeastern Univ Dept Automat Coll Informat Sci & Engn Shenyang 110819 Peoples R China Hong Kong Polytech Univ Dept Logist & Maritime Studies Kowloon Hong Kong Peoples R China Feng Chia Univ Dept Stat Taichung 40724 Taiwan Dalian Univ Technol Inst Informat & Decis Technol Sch Management Sci & Engn Dalian 116023 Peoples R China

We consider the problem of scheduling n independent and simultaneously available jobs without preemption on a single machine, where the machine has a fixed maintenance activity. The objective is to find the optimal job sequence to minimize the total amount of late work, where the late work of a job is the amount of processing of the job that is performed after its due date. We first discuss the approximability of the problem. We then develop two pseudo-polynomial dynamic programming algorithms and a fully polynomial-time approximation scheme for the problem. Finally, we conduct extensive numerical studies to evaluate the performance of the proposed algorithms. (C) 2016 Wiley Periodicals, Inc.

关键词： scheduling late work fully polynomial-time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

On the sum-product ratio problem and its applications

引用

OPERATIONS RESEARCH LETTERS 2016年第3期44卷 409-414页

作者： Wang, Ruxian Johns Hopkins Carey Business Sch Baltimore MD 21202 USA

We study the so-called sum-product ratio problem, under which the numerator is the sum of numbers in a subset and the denominator is the product of numbers in the same subset. Unlike the sum-sum ratio problem, which corresponds to the assortment problem under the multinomial logit model, the sum-product ratio problem is generally NP-complete. We develop a fully polynomial-time approximation scheme and discuss several potential applications and useful extensions. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Sum product ratio NP-hardness fully polynomial-time approximation scheme Consideration set

来源：评论

学校读者我要写书评

暂无评论

Two-agent single-machine scheduling to minimize the batch delivery cost

引用

COMPUTERS & INDUSTRIAL ENGINEERING 2016年 92卷 16-30页

作者： Yin, Yunqiang Wang, Yan Cheng, T. C. E. Wang, Du-Juan Wu, Chin-Chia Kunming Univ Sci & Technol Fac Sci Kunming 650093 Peoples R China Hong Kong Polytech Univ Dept Logist & Maritime Studies Kowloon Hong Kong Peoples R China Dalian Univ Technol Sch Management Sci & Engn Dalian 116023 Peoples R China Feng Chia Univ Dept Stat Taichung 40724 Taiwan

We consider integrated production and batch delivery scheduling in a make-to-order production system involving two competing agents, each of which having its own job set competes to process its jobs on a shared single machine. To save the delivery cost, the jobs of the same agent can be processed and delivered together batches. The completion time of each job in the same batch coincides with the batch completion time. A batch setup time is incurred before the processing of the first job in each batch. Each of the agents wants to minimize an objective function depending on the completion times of its own jobs. The goal is to determine a schedule for all the jobs of the two agents that minimizes the objective function of one agent, while keeping the objective function value of the other agent below or at a given value. For each of the problems under consideration, we either provide a polynomial-time algorithm to solve it or show that it is NP-hard. In addition, for each of the NP-hard problems, we present a mixed integer linear programming (MILP) formulation and provide a pseudo-polynomial dynamic programming algorithm, establishing that it is NP-hard in the ordinary sense only, and show that it admits an efficient fully polynomial-time approximation scheme, if viable. Finally, we compare the performance of the pseudo polynomial dynamic programming algorithms against the corresponding MILP formulations with randomly generated instances. (C) 2015 Elsevier Ltd. All rights reserved.

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：