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

Scheduling resumable deteriorating jobs on a single machine with non-availability constraints

THEORETICAL COMPUTER SCIENCE 2011年第4-5期412卷 275-280页

作者： Fan, Baoqiang Li, Shisheng Zhou, Li Zhang, Liqi Ludong Univ Dept Math & Informat Yantai 264025 Peoples R China Zhengzhou Univ Dept Math Zhengzhou 450001 Peoples R China

We consider a problem of scheduling resumable deteriorating jobs on a single machine with non-availability constraints. The objective is to minimize the total completion time. We prove that the problem with a single non-availability period is NP-hard in the ordinary sense and possesses a fully polynomial-time approximation scheme. In addition, we show that there does not exist a polynomial-time approximation algorithm with a constant worst-case ratio for the problem with two or more non-availability periods, unless P = NP. (c) 2010 Elsevier B.V. All rights reserved.

关键词： Scheduling Deteriorating job Non-availability constraint 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

来源：评论

学校读者我要写书评

暂无评论

An approximation algorithm for a supply-chain scheduling problem with an assignable common due window and holding time

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2022年第4期44卷 2167-2179页

作者： Zhang, Long Zhang, Yuzhong Bai, Qingguo Qufu Normal Univ Inst Operat Res Sch Management Rizhao 276826 Shandong Peoples R China

This paper studies single machine scheduling with batch deliveries, where a common due window for all jobs has to be determined, not given in advance. The objective is to minimize the overall cost for the process and delivery. Concretely, it includes the penalty of a job being early or tardy, the cost for holding and delivering a job, and the cost incurred by a late starting or a long duration of the common due window. Observing the NP-hardness, we provide an optimal algorithm of the problem and convert it to a fully polynomial time approximation scheme for a special case.

关键词： Supply chain scheduling Due window assignment Holding time approximation algorithm fully polynomial-time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

SINGLE-MACHINE PARETO-SCHEDULING WITH MULTIPLE WEIGHTING VECTORS FOR MINIMIZING THE TOTAL WEIGHTED LATE WORKS

引用

JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION 2021年第1期19卷 456-471页

作者： Guo, Shuen Geng, Zhichao Yuan, Jinjiang Zhengzhou Univ Sch Math & Stat Zhengzhou 450001 Henan Peoples R China

In this paper, we study the single-machine Pareto-scheduling of jobs with multiple weighting vectors for minimizing the total weighted late works. Each weighting vector has its corresponding weighted late work. The goal of the problem is to find the Pareto-frontier for the weighted late works of the multiple weighting vectors. When the number of weighting vectors is arbitrary, it is implied in the literature that the problem is unary NP-hard. Then we concentrate on our research under the assumption that the number of weighting vectors is a constant. For this problem, we present a dynamic programming algorithm running in pseudo-polynomial time and a fully polynomial-time approximation scheme (FPTAS).

关键词： Key words and phrases Scheduling multiple weights weighted late work Pareto-frontier fully polynomial-time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

Efficient computation of evacuation routes on a three-dimensional geometric network

引用

COMPUTERS & INDUSTRIAL ENGINEERING 2014年 76卷 231-242页

作者： Tang, Huajun Elalouf, Amir Levner, Eugene Cheng, T. C. E. Macau Univ Sci & Technol Sch Business Macau Peoples R China Bar Ilan Univ Dept Management Ramat Gan Israel Ashkelon Acad Coll Sch Econ Ashqelon Israel Hong Kong Polytech Univ Fac Business Hong Kong Hong Kong Peoples R China

We consider a real-time emergency evacuation problem that seeks to compute a set of rapid evacuation routes in a building. Given a three-dimensional geometric structure of the evacuation network, an emergency evacuation route is a sequence of movements of people away from the threat or actual occurrence of a hazard (such as a fire, a hidden bomb) to a safe exit in the network. In such a network each room/crossing/exit in the building is designated as a node and the corridors/staircases/links between the rooms are edges. The evacuation times assigned to the edges are normally distributed random variables. This stochastic routing problem subject to deadline constraints is NP-hard. We provide a new pseudo-polynomial-time dynamic programming algorithm to solve this problem. Based on this algorithm, we construct two types of approximation algorithm, namely a fully polynomial-time approximation scheme providing "almost-optimal" solutions and a fully polynomial-time approximately feasible scheme yielding a best "almost feasible" solution. We present a case study and results of computational experiments to illustrate the working and efficacy of the proposed solution methods, respectively. (C) 2014 Elsevier Ltd. All rights reserved.

关键词： Real-time emergency routing No-notice building evacuation Dynamic programming fully polynomial-time approximation scheme fully polynomial-time approximately feasible 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

来源：评论

学校读者我要写书评

暂无评论

Minimum shared-power edge cut

引用

NETWORKS 2020年第3期75卷 321-333页

作者： Cabello, Sergio Jain, Kshitij Lubiw, Anna Mondal, Debajyoti Univ Ljubljana Dept Math Ljubljana Slovenia IMFM Ljubljana Slovenia Borealis AI Waterloo ON Canada Univ Waterloo Sch Comp Sci Waterloo ON Canada Univ Saskatchewan Dept Comp Sci Saskatoon SK Canada

We introduce a problem called minimum shared-power edge cut (MSPEC). The input to the problem is an undirected edge-weighted graph with distinguished vertices s and t, and the goal is to find an s-t cut by assigning "powers" at the vertices and removing an edge if the sum of the powers at its endpoints is at least its weight. The objective is to minimize the sum of the assigned powers. MSPEC is a graph generalization of a barrier coverage problem in a wireless sensor network: given a set of unit disks with centers in a rectangle, what is the minimum total amount by which we must shrink the disks to permit an intruder to cross the rectangle undetected, that is, without entering any disk. This is a more sophisticated measure of barrier coverage than the minimum number of disks whose removal breaks the barrier. We develop a fully polynomial time approximation scheme for MSPEC. We give polynomial time algorithms for the special cases where the edge weights are uniform, or the power values are restricted to a bounded set. Although MSPEC is related to network flow and matching problems, its computational complexity (in P or NP-hard) remains open.

关键词： activation network barrier coverage fully polynomial-time approximation scheme s-t cut wireless network

来源：评论

学校读者我要写书评

暂无评论

A COMPUTATIONALLY EFFICIENT FPTAS FOR CONVEX STOCHASTIC DYNAMIC PROGRAMS

引用

SIAM JOURNAL ON OPTIMIZATION 2015年第1期25卷 317-350页

作者： Halman, Nir Nannicini, Giacomo Orlin, James Hebrew Univ Jerusalem Jerusalem Sch Business Adm Jerusalem Israel MIT Dept Civil & Environm Engn Cambridge MA 02139 USA Singapore Univ Technol & Design Engn Syst & Design Singapore Singapore MIT Sloan Sch Management Cambridge MA 02139 USA

We propose a computationally efficient fully polynomial-time approximation scheme (FPTAS) to compute an approximation with arbitrary precision of the value function of convex stochastic dynamic programs, using the technique of K-approximation sets and functions introduced by Halman et al. [Math. Oper. Res., 34, (2009), pp. 674-685]. This paper deals with the convex case only, and it has the following contributions. First, we improve on the worst-case running time given by Halman et al. Second, we design and implement an FPTAS with excellent computational performance and show that it is faster than an exact algorithm even for small problem instances and small approximation factors, becoming orders of magnitude faster as the problem size increases. Third, we show that with careful algorithm design, the errors introduced by floating point computations can be bounded, so that we can provide a guarantee on the approximation factor over an exact infinite-precision solution. We provide an extensive computational evaluation based on randomly generated problem instances coming from applications in supply chain management and finance. The running time of the FPTAS is both theoretically and experimentally linear in the size of the uncertainty set.

关键词： dynamic programming approximation algorithms inventory control fully polynomial-time approximation scheme discrete convexity

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：