<?xml version="1.0" encoding="UTF-8"?><?xml-stylesheet type="text/xsl" href="static/style.xsl"?><OAI-PMH xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd"><responseDate>2026-11-22T15:32:41Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/2916" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/2916</identifier><datestamp>2017-03-21T19:49:56Z</datestamp><setSpec>com_10012_9924</setSpec><setSpec>com_10012_1</setSpec><setSpec>col_10012_9930</setSpec><setSpec>col_10012_6</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:doc="http://www.lyncode.com/xoai" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="author" lang="en" authority="e5859468-9bb1-4e7a-86f3-eff6e553e74f" confidence="600">Quimper, Claude-Guy</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2007-05-08T14:00:33Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2007-05-08T14:00:33Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued" lang="en">2006</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted" lang="en">2006</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/2916</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">We study in this thesis three well known global constraints.   The All-Different constraint restricts a set of variables to be assigned to distinct values.   The &amp;lt;em&amp;gt;global cardinality constraint&amp;lt;/em&amp;gt; (GCC) ensures that a value &amp;lt;em&amp;gt;v&amp;lt;/em&amp;gt; is assigned to at least &amp;lt;em&amp;gt;l&amp;lt;sub&amp;gt;v&amp;lt;/sub&amp;gt;&amp;lt;/em&amp;gt; variables and to at most &amp;lt;em&amp;gt;u&amp;lt;sub&amp;gt;v&amp;lt;/sub&amp;gt;&amp;lt;/em&amp;gt; variables among a set of given variables where &amp;lt;em&amp;gt;l&amp;lt;sub&amp;gt;v&amp;lt;/sub&amp;gt;&amp;lt;/em&amp;gt; and &amp;lt;em&amp;gt;u&amp;lt;sub&amp;gt;v&amp;lt;/sub&amp;gt;&amp;lt;/em&amp;gt; are non-negative integers such that &amp;lt;em&amp;gt;l&amp;lt;sub&amp;gt;v&amp;lt;/sub&amp;gt;&amp;lt;/em&amp;gt;  &amp;amp;le; &amp;lt;em&amp;gt;u&amp;lt;sub&amp;gt;v&amp;lt;/sub&amp;gt;&amp;lt;/em&amp;gt;.   The Inter-Distance constraint ensures that all variables, among a set of variables &amp;lt;em&amp;gt;x&amp;lt;/em&amp;gt;&amp;lt;sub&amp;gt;1&amp;lt;/sub&amp;gt;, .  .  .  , &amp;lt;em&amp;gt;x&amp;lt;sub&amp;gt;n&amp;lt;/sub&amp;gt;&amp;lt;/em&amp;gt;, are pairwise distant from &amp;lt;em&amp;gt;p&amp;lt;/em&amp;gt;, i.  e.   |&amp;lt;em&amp;gt;x&amp;lt;sub&amp;gt;i&amp;lt;/sub&amp;gt;&amp;lt;/em&amp;gt; - &amp;lt;em&amp;gt;x&amp;lt;sub&amp;gt;j&amp;lt;/sub&amp;gt;&amp;lt;/em&amp;gt;| &amp;amp;ge; &amp;lt;em&amp;gt;p&amp;lt;/em&amp;gt; for all &amp;lt;em&amp;gt;i&amp;lt;/em&amp;gt; &amp;amp;ne; &amp;lt;em&amp;gt;j&amp;lt;/em&amp;gt;.   The All-Different constraint, the GCC, and the Inter-Distance constraint are largely used in scheduling problems.   For instance, in scheduling problems where tasks with unit processing time compete for a single resource, we have an All-Different constraint on the starting time variables.   When there are &amp;lt;em&amp;gt;k&amp;lt;/em&amp;gt; resources, we have a GCC with &amp;lt;em&amp;gt;l&amp;lt;sub&amp;gt;v&amp;lt;/sub&amp;gt;&amp;lt;/em&amp;gt; = 0 and &amp;lt;em&amp;gt;u&amp;lt;sub&amp;gt;v&amp;lt;/sub&amp;gt;&amp;lt;/em&amp;gt; = &amp;lt;em&amp;gt;k&amp;lt;/em&amp;gt; over all starting time variables.   Finally, if tasks have processing time &amp;lt;em&amp;gt;t&amp;lt;/em&amp;gt; and compete for a single resource, we have an Inter-Distance constraint with &amp;lt;em&amp;gt;p&amp;lt;/em&amp;gt; = &amp;lt;em&amp;gt;t&amp;lt;/em&amp;gt; over all starting time variables.   We present new propagators for the All-Different constraint, the GCC, and the Inter-Distance constraint i.  e.  , new filtering algorithms that reduce the search space according to these constraints.   For a given consistency, our propagators outperform previous propagators both in practice and in theory.   The gains in performance are achieved through judicious use of advanced data structures combined with novel results on the structural properties of the constraints.</dim:field>
   <dim:field mdschema="dc" element="format" lang="en">application/pdf</dim:field>
   <dim:field mdschema="dc" element="format" qualifier="extent">983035 bytes</dim:field>
   <dim:field mdschema="dc" element="format" qualifier="mimetype">application/pdf</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso" lang="en">en</dim:field>
   <dim:field mdschema="dc" element="publisher" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="dc" element="rights" lang="en">Copyright: 2006, 
  Quimper, Claude-Guy. All rights reserved.</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Computer Science</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Constraint Programming</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Global Constraints</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Propagators</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">All-Different constraint</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Global Cardinality Constraint</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">GCC</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Inter-Distance Constraint</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">Efficient Propagators for Global Constraints</dim:field>
   <dim:field mdschema="dc" element="type" lang="en">Doctoral Thesis</dim:field>
   <dim:field mdschema="dc" element="pending" lang="en">false</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="department" lang="en">School of Computer Science</dim:field>
   <dim:field mdschema="uws-etd" element="degree" lang="en">Doctor of Philosophy</dim:field>
   <dim:field mdschema="uws" element="typeOfResource" lang="en">Text</dim:field>
   <dim:field mdschema="uws" element="peerReviewStatus" lang="en">Unreviewed</dim:field>
   <dim:field mdschema="uws" element="scholarLevel" lang="en">Graduate</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>