A Fully Polynomial Approximation Scheme for Minimizing Makespan of Deteriorating Jobs

被引：76

作者：

Kovalyov M.Y. ^{[1
]}

Kubiak W. ^{[2
]}

机构：

[1] Institute of Engineering Cybernetics, Natl. Academy of Sciences of Belarus, Surganova 6

[2] Faculty of Business Administration, Memorial University of Newfoundland, St. John's

来源：

Journal of Heuristics | 1998年 / 3卷 / 4期

基金：

加拿大自然科学与工程研究理事会;

关键词：

Deteriorating jobs; Fully polynomial approximation scheme;

D O I：

10.1023/A:1009626427432

中图分类号：

学科分类号：

摘要：

A fully polynomial approximation scheme for the problem of scheduling n deteriorating jobs on a single machine to minimize makespan is presented. Each algorithm of the scheme runs in O(n5L4/∈3) time, where L is the number of bits in the binary encoding of the largest numerical parameter in the input, and ∈ is required relative error. The idea behind the scheme is rather general and it can be used to develop fully polynomial approximation schemes for other combinatorial optimization problems. Main feature of the scheme is that it does not require any prior knowledge of lower and/or upper bounds on the value of optimal solutions.

引用

页码：287 / 297

页数：10

共 18 条

[1]

Browne, S., Yechiali, U., Dynamic Priority Rules for Cyclic Type Queues (1989) Advances in Applied Probability, 10, pp. 432-450

[2]

Browne, S., Yechiali, U., Scheduling Deteriorating Jobs on a Single Processor (1990) Operations Research, 38, pp. 495-498

[3]

Gens, G.V., Levner, E.V., Fast Approximation Algorithms for Knapsack Type Problems (1980) Lecture Notes in Control and Information Science, 23, pp. 185-194

[4]

Gupta, S.K., Kunnathur, A.S., Dandapani, K., Optimal Repayment Policies for Multiple Loans (1988) OMEGA, 15, pp. 207-227

[5]

Horowitz, E., Sahni, S., Exact and Approximate Algorithms for Scheduling Nonidentical Processors (1976) Journal ACM, 23, pp. 317-327

[6]

Ibarra, O.H., Kim, C.E., Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems (1975) Journal ACM, 22, pp. 463-468

[7]

Johnson, D.S., Niemi, K.A., On Knapsacks, Partitions, and a New Dynamic Programming Technique for Trees (1983) Mathematics of Operations Research, 8, pp. 1-14

[8]

Karp, R.M., The Fast Approximate Solution of Hard Combinatorial Problems (1975) Proc. 6th Southeastern Conference on Combinatorics, Graph Theory, and Computing, pp. 15-31. , Winnipeg: Utilitas Mathematica Publishing

[9]

Kovalyov, M.Y., Shafransky, Y.M., Strusevich, V.A., Tanaev, V.S., Tuzikov, A.V., Approximation Scheduling Algorithms: A Survey (1989) Optimization, 20, pp. 859-878

[10]

Kovalyov, M.Y., Potts, C.N., Van Wassenhove, L.N., A Fully Polynomial Approximation Scheme for Scheduling a Single Machine to Minimize Total Weighted Late Work (1994) Mathematics of Operations Research, 19, pp. 86-93

← 1 2 →