Minimizing maximum lateness under linear deterioration

被引：79

作者：

Bachman, A ^{[1
]}

Janiak, A ^{[1
]}

机构：

[1] Wroclaw Univ Technol, Inst Engn Cybernet, PL-50372 Wroclaw, Poland

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 2000年 / 126卷 / 03期

关键词：

complexity; scheduling theory; single machine; deteriorating jobs; due date;

D O I：

10.1016/S0377-2217(99)00310-0

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

The paper deals with a single machine scheduling problem, where job processing time is given as a start time dependent linear function. The objective is to find such a schedule (processing order) which minimizes the maximum lateness criterion. We show that the problem is NP-complete and present two heuristic algorithms. An experimental analysis of the proposed algorithms is also given. (C) 2000 Elsevier Science B.V. All rights reserved.

引用

页码：557 / 566

页数：10

共 8 条

[1]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[2]

Bachman A., 1997, 3497 WROCL U TECHN I

[3] SCHEDULING DETERIORATING JOBS ON A SINGLE PROCESSOR [J].

BROWNE, S ;

YECHIALI, U .

OPERATIONS RESEARCH, 1990, 38 (03) :495-498

[4]

GAWIEJNOWICZ L, 1995, 0271995 A MICK U FAC

[5]

Jackson J. R., 1956, Naval Research Logistics Quarterly, V3, P201

[6] MINIMIZING THE MAKESPAN WITH LATE START PENALTIES ADDED TO PROCESSING TIMES IN A SINGLE FACILITY SCHEDULING PROBLEM [J].

KUNNATHUR, AS ;

GUPTA, SK .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1990, 47 (01) :56-64

[7] SCHEDULING JOBS UNDER SIMPLE LINEAR DETERIORATION [J].

MOSHEIOV, G .

COMPUTERS & OPERATIONS RESEARCH, 1994, 21 (06) :653-659

[8] SINGLE-MACHINE SCHEDULING WITH START TIME-DEPENDENT PROCESSING TIMES - SOME SOLVABLE CASES [J].

SUNDARARAGHAVAN, PS ;

KUNNATHUR, AS .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1994, 78 (03) :394-403

← 1 →