Title

Scheduling Start Time Dependent Tasks with Deadlines and Identical Initial Processing Times on a Single Machine

Publication Type

Journal Article

Publication Date

2003

Abstract

In this paper, we study the feasibility problem of scheduling a set of start time dependent tasks on a single machine with deadlines, processing rates and identical initial processing times. First, we show that the cases with arbitrary deadlines are strongly NP-complete. Second, we show that the cases with two distinct deadlines are NP-complete in the ordinary sense. Finally, we give an optimal polynomial algorithm for the makespan problem with two distinct processing rates. We solve a series of open problems in the literature and give a sharp boundary delineating the complexity of the problems.

Keywords

Sequencing, Time dependence scheduling, Computational complexity

Discipline

Business

Research Areas

Operations Management

Publication

Computers and Operations Research

Volume

30

Issue

1

First Page

51

Last Page

62

ISSN

0305-0548

Identifier

10.1016/s0305-0548(01)00077-6

Publisher

Elsevier