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

Single-machine parallel-batching scheduling with family jobs to minimize weighted number of tardy jobs

COMPUTERS & INDUSTRIAL ENGINEERING 2014年第1期73卷 5-10页

作者： Li, Shi-Sheng Chen, Ren-Xia Zhongyuan Univ Technol Coll Sci Zhengzhou 450007 Peoples R China

We consider the problem of scheduling n jobs in batches on a single parallel-batching machine, where the jobs are partitioned into jobs families and the jobs in each family have the same due date. The objective is to minimize the weighted number of tardy jobs. We first devise an efficient pseudo-polynomial time and a fully polynomial time approximation scheme for the weighted problem. Then we present O(n(2))-time and O(n log n)-time algorithms for the case where the jobs have the same weight and for the case where the jobs have the same processing time, respectively. (C) 2014 Elsevier Ltd. All rights reserved.

关键词： Parallel-batching scheduling Family jobs Uniform family due dates fully polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

An FPTAS for a single-item capacitated economic lot-sizing problem with monotone cost structure

引用

MATHEMATICAL PROGRAMMING 2006年第3期106卷 453-466页

作者： Chubanov, S Kovalyov, MY Pesch, E Belarusian State Univ Fac Econ Minsk 220050 BELARUS Univ Siegen Inst Informat Syst Siegen Germany Natl Acad Sci Belarus United Inst Informat Problems Minsk 220050 BELARUS

We present a fully polynomial time approximation scheme (FPTAS) for a capacitated economic lot-sizing problem with a monotone cost structure. An FPTAS delivers a solution with a given relative error epsilon in time polynomial in the problem size and in 1/epsilon. Such a scheme was developed by van Hoesel and Wagelmans [8] for a capacitated economic lot-sizing problem with monotone concave (convex) production and backlogging cost functions. We omit concavity and convexity restrictions. Furthermore, we take advantage of a straightforward dynamic programming algorithm applied to a rounded problem.

关键词： capacitated economic lot-sizing problem dynamic programming fully polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

Uniform Parallel-Machine Scheduling with time Dependent Processing times

引用

Journal of the Operations Research Society of China 2013年第2期1卷 239-252页

作者： Juan Zou Yuzhong Zhang Cuixia Miao School of Management Qufu Normal UniversityRizhaoShandongChina School of Mathematical Sciences Qufu Normal UniversityQufuShandongChina

We consider several uniform parallel-machine scheduling problems in which the processing time of a job is a linear increasing function of its starting *** objectives are to minimize the total completion time of all jobs and the total load on all *** show that the problems are polynomially solvable when the increasing rates are identical for all jobs;we propose a fully polynomial-time approximation scheme for the standard linear deteriorating function,where the objective function is to minimize the total load on all *** also consider the problem in which the processing time of a job is a simple linear increasing function of its starting time and each job has a delivery *** objective is to find a schedule which minimizes the time by which all jobs are delivered,and we propose a fully polynomial-time approximation scheme to solve this problem.

关键词： Scheduling Uniform machine Linear deterioration fully polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

Scheduling problems with rejection and piece-rate maintenance to minimise the total weighted completion time

引用

INTERNATIONAL JOURNAL OF AUTOMATION AND CONTROL 2022年第1期16卷 64-86页

作者： Yu, Xianyu Wang, Zhen Huang, Kai Xu, Dehua Sang, Xiuzhi Nanjing Univ Aeronaut & Astronaut Coll Econ & Management 29 Jiangjun Ave Nanjing 211106 Peoples R China McMaster Univ DeGroote Sch Business Hamilton ON L8S 4M4 Canada Nanjing Univ Finance & Econ Sch Int Econ & Business 3 Wenyuan Ave Nanjing 210023 Peoples R China

This paper addresses the single machine scheduling problems with simultaneous consideration of rejection and piece-rate maintenance. Each job is either accepted to be processed on the machine, or rejected in which case a rejection penalty will be incurred. The piece-rate maintenance refers that the machine performs maintenance activity every time it completes a given number of jobs. The objective is to minimise the sum of weighted completion times, rejection costs and maintenance costs. Our contribution is threefold. First, the general case of the considered problem is proved to be NP-hard, and an approximate algorithm is developed to solve the problem. Second, for the case with agreeable condition that jobs with smaller processing times are weighted more, a pseudo-polynomial algorithm is developed to establish that the problem is NP-hard only in the ordinary sense. This pseudo-polynomial algorithm is further converted into a fully polynomial time approximation scheme (FPTAS). In the third, two special cases, in which one with all equal weights and the other one with all equal processing times, are proved to be solved in polynomial time.

关键词： scheduling rejection maintenance agreeable condition fully polynomial time approximation scheme FPTAS

来源：评论

学校读者我要写书评

暂无评论

Vector scheduling with rejection on a single machine

引用

4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH 2018年第1期16卷 95-104页

作者： Li, Weidong Cui, Qianna Yunnan Univ Kunming 650091 Yunnan Peoples R China Yunnan Univ Dianchi Coll Kunming 650228 Yunnan Peoples R China

In this paper, we study a vector scheduling problem with rejection on a single machine, in which each job is characterized by a d-dimension vector and a penalty, in the sense that, jobs can be either rejected by paying a certain penalty or assigned to the machine. The objective is to minimize the sum of the maximum load over all dimensions of the total vector of all accepted jobs, and the total penalty of rejected jobs. We prove that the problem is NP-hard and design two approximation algorithms running in polynomial time. When d is a fixed constant, we present a fully polynomial time approximation scheme.

关键词： Vector scheduling approximation algorithms Dynamic programming fully polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

Positive half-products and scheduling with controllable processing times

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2005年第2期165卷 416-422页

作者： Janiak, A Kovalyov, MY Kubiak, W Werner, F Mem Univ Newfoundland Fac Business Adm St John NF A1B 3X5 Canada Wroclaw Univ Technol Inst Engn Cybernet Wroclaw Poland Belarusian State Univ Fac Econ Minsk 220050 BELARUS Natl Acad Sci Belarus United Inst Informat Problems Minsk 220050 BELARUS Otto Von Guericke Univ Magdeburg Germany

We study the single machine scheduling problem with controllable job processing times to minimize a linear combination of the total weighted job completion time and the total weighted processing time compression. We show that this scheduling problem is a positive half-product minimization problem. Positive half-products make up an interesting subclass of half-products and are introduced in this paper to provide a conceptual framework for the problem with controllable job processing times as well as other problems. This framework allows to readily derive in one fell swoop a number of results for the problem with controllable processing times from more general results obtained earlier for the half-product. We also present fast fully polynomial time approximation schemes for the problem with controllable processing times. The schemes apply to all positive half-products. (c) 2004 Elsevier B.V. All rights reserved.

关键词： single machine scheduling controllable processing times pseudo-Boolean optimization fully polynomial time approximation scheme computational complexity

来源：评论

学校读者我要写书评

暂无评论

FAST approximation schemeS FOR CONVEX-PROGRAMS WITH MANY BLOCKS AND COUPLING CONSTRAINTS

引用

SIAM JOURNAL ON OPTIMIZATION 1994年第1期4卷 86-107页

作者： GRIGORIADIS, MD KHACHIYAN, LG

This paper presents block-coordinate descent algorithms for the approximate solution of large structured convex programming problems. The constraints of such problems consist of K disjoint convex compact sets B-k called blocks, and M nonnegative-valued convex block-separable inequalities called coupling or resource constraints. The algorithms are based on an exponential po- tential function reduction technique. It is shown that feasibility as well as min-max resource-sharing problems for such constraints can be solved to a relative accuracy E in O(K ln M(epsilon(-2) + In K)) iterations, each of which solves K block problems to a comparable accuracy, either sequentially or in parallel. The same bound holds for the expected number of iterations of a randomized variant of the algorithm which uniformly selects a random block to process at each iteration. An extension to objective and constraint functions of arbitrary sign is also presented. The above results yield fast approximation schemes for a number of applications such as problems with additively separable functions, generalized concurrent hows with side constraints, linear and nonlinear supply-sharing transportation networks, and deterministic equivalents of certain two-stage stochastic programs. Another consequence of this analysis is that, for a fixed relative accuracy, the approximate solution of matrix games is in NC.

关键词： approximation ALGORITHM BLOCK ANGULAR OPTIMIZATION COMPLEXITY EXPONENTIAL POTENTIAL FUNCTION fully polynomial time approximation scheme LINEAR PROGRAMMING MULTICOMMODITY FLOW NONLINEAR PROGRAMMING PARALLEL COMPUTATION RANDOMIZED ALGORITHM STRUCTURED OPTIMIZATION

来源：评论

学校读者我要写书评

暂无评论

A half-product based approximation scheme for agreeably weighted completion time variance

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2005年第1期162卷 45-54页

作者： Cheng, JL Kubiak, W Mem Univ Newfoundland Fac Business Adm St Johns NF A1B 3X5 Canada

A recent INFORMS Journal on Computing paper presents a fully polynomial time approximation scheme for minimizing the completion time variance with agreeable weights on a single machine. This paper presents a much fast... 详细信息

关键词： scheduling fully polynomial time approximation scheme weighted completion time variance agreeable weights half-products

来源：评论

学校读者我要写书评

暂无评论

DIAMETER-CONSTRAINED STEINER TREES

引用

DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS 2011年第4期3卷 491-502页

作者： Ding, Wei Lin, Guohui Xue, Guoliang Zhejiang Water Conservancy & Hydropower Coll Hangzhou 310018 Zhejiang Peoples R China Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada Arizona State Univ Dept Comp Sci & Engn Tempe AZ 85287 USA

Given an edge-weighted undirected graph G = (V, E, c, w), where each edge e epsilon E has a non-negative cost c(e) and a non-negative weight w(e), a set S subset of V of terminals and a positive constant D-0, we seek a minimum cost Steiner tree in which all terminals appear as leaves and the tree diameter is bounded by D-0. Here the tree diameter is the maximum weight of the paths connecting two different leaves in the tree. Such a problem is called the minimum cost diameter-constrained Steiner tree problem. The problem is NP-hard even when the topology of the Steiner tree is fixed. In present paper we focus on this fixed topology restricted version and present a fully polynomial time approximation scheme for computing a minimum cost diameter-constrained Steiner tree.

关键词： Diameter-constrained Steiner tree fully polynomial time approximation scheme fixed topology

来源：评论

学校读者我要写书评

暂无评论

Parallel-Machine Scheduling Problem under the Job Rejection Constraint (Extended Abstract)

Parallel-Machine Scheduling Problem under the Job Rejection ...

引用

8th International Frontiers of Algorithmics Workshop (FAW)

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

ISBN: (纸本)9783319080161;9783319080154

Given m identical machines and n independent jobs, each job J(j) has a processing time (or size) p(j) and a penalty e(j). A job can be either rejected, in which case its penalty is paid, or scheduled on one of the machines, in which case its processing time contributes to the load of that machine. The objective is to minimize the makespan of the schedule for accepted jobs under the constraint that the total penalty of the rejected jobs is no more than a given bound B. In this paper, we present a 2-approximation algorithm within strongly polynomial time and a polynomial time approximation scheme whose running time is O(nm O(1/e(2)) + mn(2)) for the general case. Moreover, we present a fully polynomial time approximation scheme for the case where the number of machines is a fixed constant. This result improves previous best running time from O(n(m+2) /epsilon(m)) to O(1/epsilon(2m+3) + mn(2)).

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：