AN IMPROVED APPROXIMATION SCHEME FOR SCHEDULING A MAINTENANCE AND PROPORTIONAL DETERIORATING JOBS

被引：12

作者：

Kacem, Imed ^{[1
]}

Levner, Eugene ^{[2
,3
]}

机构：

[1] Univ Lorraine, LCOMS EA 7306, F-57000 Metz, France

[2] Ashkelon Acad Coll, Sch Econ, IL-78211 Ashqelon, Israel

[3] Holon Inst Technol, Dept Comp Sci, IL-5810201 Holon, Israel

来源：

JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION | 2016年 / 12卷 / 03期

基金：

中国国家自然科学基金;

关键词：

Scheduling; deteriorating jobs; total completion time; maintenance activities; approximation scheme; AVAILABILITY CONSTRAINT; SINGLE-MACHINE; SUBJECT;

D O I：

10.3934/jimo.2016.12.811

中图分类号：

T [工业技术];

学科分类号：

08 ;

摘要：

In this paper, we re-visit the problem of scheduling a set of proportional deteriorating non-resumable jobs on a single machine subject to maintenance. The maintenance has to be started prior to a given deadline. The jobs as well as the maintenance are to be scheduled so that to minimize the total completion time. For this problem we propose a new dynamic programming algorithm and a faster fully polynomial time approximation scheme improving a recent result by Luo and Chen [JIMO (2012), 8:2, 271-283].

引用

页码：811 / 817

页数：7

共 11 条

[1]

Gawiejnowicz S., 2008, EATC MONOGRAPH THEOR

[2] Scheduling deteriorating jobs subject to job or machine availability constraints [J].

Gawiejnowicz, Stanislaw .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2007, 180 (01) :472-478

[3] Complexity and approximability of scheduling resumable proportionally deteriorating jobs [J].

Gawiejnowicz, Stanislaw ;

Kononov, Alexander .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2010, 200 (01) :305-308

[4] FAST APPROXIMATION ALGORITHM FOR JOB SEQUENCING WITH DEADLINES [J].

GENS, GV ;

LEVNER, EV .

DISCRETE APPLIED MATHEMATICS, 1981, 3 (04) :313-318

[5] Scheduling linear deteriorating jobs with an availability constraint on a single machine [J].

Ji, Min ;

He, Yong ;

Cheng, T. C. E. .

THEORETICAL COMPUTER SCIENCE, 2006, 362 (1-3) :115-126

[6] Approximation schemes for scheduling on a single machine subject to cumulative deterioration and maintenance [J].

Kellerer, Hans ;

Rustogi, Kabir ;

Strusevich, Vitaly A. .

JOURNAL OF SCHEDULING, 2013, 16 (06) :675-683

[7] Machine scheduling with an availability constraint [J].

Lee, CY .

JOURNAL OF GLOBAL OPTIMIZATION, 1996, 9 (3-4) :395-416

[8] APPROXIMATION SCHEMES FOR SCHEDULING A MAINTENANCE AND LINEAR DETERIORATING JOBS [J].

Luo, Wenchang ;

Chen, Lin .

JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION, 2012, 8 (02) :271-283

[9] A FPTAS for minimizing total completion time in a single machine time-dependent scheduling problem [J].

Ocetkiewicz, Krzysztof M. .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2010, 203 (02) :316-320

[10] When does a dynamic programming formulation guarantee the existence of a fully polynomial time approximation scheme (FPTAS)? [J].

Woeginger, GJ .

INFORMS JOURNAL ON COMPUTING, 2000, 12 (01) :57-74

← 1 2 →