Complexity of some special types of timetabling problems

DOI10.1002/jos.97zbMath0996.90039MaRDI 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 coloring; timetabling; NP-complete; chromatic index

Mathematics Subject Classification ID

90C60: Abstract computational complexity for mathematical programming problems

90B35: Deterministic scheduling theory in operations research

Related Items

Mathematical models and algorithms for a high school timetabling problem, 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, A computational study of a cutting plane algorithm for university course timetabling, A computational study of local search algorithms for Italian high-school timetabling, A projective algorithm for preemptive open shop scheduling with two multiprocessor groups, A simulated annealing with a new neighborhood structure based algorithm for high school timetabling problems, A new model for automated examination timetabling

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