Complexity of some special types of timetabling problems

DOI10.1002/jos.97zbMath0996.90039OpenAlexW1984680233MaRDI QIDQ1600003

R. Smith

Publication date: 6 June 2002

Published in: Journal of Scheduling (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/jos.97

zbMATH Keywords

edge coloringtimetablingNP-completechromatic index

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35)

Related Items (12)

Preemptive open shop scheduling with multiprocessors: Polynomial cases and applications ⋮ A survey of search methodologies and automated system development for examination timetabling ⋮ School timetabling for quality student and teacher schedules ⋮ Mathematical models and algorithms for a high school timetabling problem ⋮ An effective hybrid local search approach for the post enrolment course timetabling problem ⋮ A computational study of a cutting plane algorithm for university course timetabling ⋮ A computational study of local search algorithms for Italian high-school timetabling ⋮ Four decades of research on the open-shop scheduling problem to minimize the makespan ⋮ A new model for automated examination timetabling ⋮ A projective algorithm for preemptive open shop scheduling with two multiprocessor groups ⋮ On a conjecture for the university timetabling problem ⋮ A simulated annealing with a new neighborhood structure based algorithm for high school timetabling problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An introduction to timetabling
• Some preemptive open shop scheduling problems with a renewable or a nonrenewable resource
• Extensions of coloring models for scheduling purposes
• The combinatorics of timetabling
• Investigation on interval edge-colorings of graphs
• Restricted coloring models for timetabling
• Open shop problem with zero-one time operations and integer release date/deadline intervals
• On the Complexity of Timetable and Multicommodity Flow Problems

This page was built for publication: Complexity of some special types of timetabling problems