Scheduling around a small common due date
January 1991
Article
pp 237-242.
This publication is part of collection
| Related Files |
|---|
View PDF Version
(SchedulingAround_1991.pdf, 0.4MB) |
|
Redirect to publisher's version
(publisher's version.url.txt, 18 bytes) |
A set of n jobs has to be scheduled on a single machine which can handle only one job at a time. Each job requires a given positive uninterrupted processing time and has a positive weight. The problem is to find a schedule that minimizes the sum of weighted deviations of the job completion times from a given common due date d, which is smaller than the sum of the processing times. We prove that this problem is NP-hard even if all job weights are equal. In addition, we present a pseudopolynomial algorithm that requires O(n2d) time and O(nd) space.
Keywords
Automatically Extracted Terms
- problem
- schedule
- scheduling
- completion
- weight
- processing
- algorithm
- velde / scheduling
- theorem
- t h e
- research
- partition
- processing times
- completion times
- completion time
- tardiness penalty weights
- even-odd partition problem
- time t
- time 0
- tardiness
