Name
Title | ||
|---|---|---|
Scheduling unit time jobs with integer release dates to minimize the weighted number of tardy jobs |
Abstract | ||
|---|---|---|
Consider a set of n unit time jobs, each one having a release date, a due date, both nonnegative integers, and a weight, a positive real number.
Given a set of m parallel machines, we describe an algorithm for finding schedules with minimum weighted number of tardy jobs. The complexity
of the proposed algorithm is
. The best previous algorithm for this problem has complexity O(mn
3) and employs network flow techniques. Our method is based on a characterization for schedules of this type and employs graph
theoretic tools. |
Year | DOI | Venue |
|---|---|---|
2009 | https://doi.org/10.1007/s10479-008-0479-y | Annals of Operations Research |
Keywords | Field | DocType |
Algorithms,Graph theory,Parallel machines,Scheduling theory,Tardy jobs,Unit time jobs | Flow network,Graph theory,Integer,Discrete mathematics,Graph,Mathematical optimization,Release date,Scheduling (computing),Schedule,Real number,Mathematics | Journal |
Volume | Issue | ISSN |
169 | 1 | 0254-5330 |
Citations | PageRank | References |
4 | 0.58 | 4 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mitre Dourado | 1 | 90 | 18.43 |
| Rosiane de Freitas Rodrigues | 2 | 11 | 3.14 |
| Jayme Luiz Szwarcfiter | 3 | 618 | 95.79 |