Distributed University Timetabling with Multiply Sectioned Constraint Networks

Yang Xiang, Wanling Zhang

Although timetabling has long been studied through constraint satisfaction based techniques, along with many alternatives, only recently work has been reported where distributed timetabling problems (DisTTPs) was studied as distributed constraint satisfaction problems (DisCSPs). We present an alternative method for solving DisTTPs based on multiply sectioned constraint networks (MSCNs). The proposed solution has several distinguishing features: Unlike the existing algorithms for DisCSPs whose worst-case time complexities are exponential, the algorithm suite based on MSCNs is efficient when the network topology is sparse. Unlike the existing DisTTP algorithm where a central agent is needed, there is no need for a central agent in the proposed solution. Unlike the existing DisTTP algorithm where partial timetables of other agents must be disclosed to the central agent, the proposed method keeps partial timetables of all agents private. We report our preliminary experimental result on distributed university timetabling problems (DisUTTPs).

Subjects: 15.2 Constraint Satisfaction; 1.12 Scheduling

Submitted: Feb 10, 2008

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.