Approximation Algorithms for Fixed Job Schedule Problems

Matteo Fischetti · Silvano Martello · Paolo Toth

47 citations0/0 files storedOperations Research

No readable copy stored yet — this record is metadata only.

No open-access location is known for this record yet.

Literature note Cite in a project Citation map

Scheduling and Timetabling Solutions Complexity and Algorithms in Graphs Scheduling and Optimization Algorithms

Abstract

We consider two generalizations of the fixed job schedule problem, obtained by imposing a bound on the spread-time or on the working time of each processor. These NP-hard problems, studied by the authors in previous works, can arise in bus driver scheduling. We introduce several polynomial-time approximation algorithms, give efficient implementations for them, and analyze their complexity and worst case performance. The average behavior is also investigated through extensive computational experiments.

Paper brief

Loading…

Cite this work

Citation unavailable for this work.

BibTeX RIS CSL-JSON

No public copy is stored for this record, so only the metadata is cited.

Citations in this library

Citation map →

Stored only when both papers are in the corpus — 47 citations exist upstream.

References

1987The Fixed Job Schedule Problem with Spread-Time Constraints 1986A heuristic approach to the bus driver scheduling problem

Cited by

2001The Personnel Task Scheduling Problem

Explore the map →

Papers that cite the same references — the relational fallback while embeddings are still backfilling.

Imported from OpenAlex (CC0) — nothing here is generated.