Citation
Retractable Contract Network for Distributed Scheduling. In proceedings of the 2nd Multidisciplinary International Conference on Scheduling : Theory and Applications (MISTA 2005), 18 -21 July 2005, New York, USA, pages 485-500, 2005.
Paper
Abstract
This paper is about distributed scheduling where individual agents have potentially conflicting interests. It is motivated by BT’s workforce scheduling problem, where multiple service providers have to serve multiple service buyers. The service providers and buyers all attempt to maximize their own utility. The overall problem is a multi-objective optimization problem; for example, one has to maximize completion rates and service quality and minimize travelling distances. In this paper, BT’s problem is modelled as an open constraint optimization system. Standard contract net is a practical strategy in distributed scheduling where agents may have conflicting objectives. In this paper, we have introduced a retractable contract net protocol, which we call RECONNET, that supports hill-climbing in the space of solutions. It is built upon a job-release and compensation mechanism. RECONNET is a general protocol, which could be used to implement complex meta-heuristic algorithms such as Tabu Search and Guided Local Search. A system based on RECONNET has been implemented for BT’s workforce scheduling problem. The software, which we call ASMCR, allows the management to have full control over the company’s multiobjectives. The manager generates a Pareto set of solution by defining, for each buyer and seller, the weights given to each objective. ASMCR gives service buyers and sellers ownership of their problem and freedom to maximize their performance under the criteria defined by the management. ASMCR took 5 to 15 minutes to complete when tested on real-sized problems. It has potential to be developed into practical solutions to BT’s workforce scheduling problem.
You can download the pdf of this publication from here
doi
This publication does not have a doi, so we cannot provide a link to the original source
What is a doi?: A doi (Document Object Identifier) is a unique identifier for sicientific papers (and occasionally other material). This provides direct access to the location where the original article is published using the URL http://dx.doi/org/xxxx (replacing xxx with the doi). See http://dx.doi.org/ for more information
URL
This pubication does not have a URL associated with it.
The URL is only provided if there is additional information that might be useful. For example, where the entry is a book chapter, the URL might link to the book itself.
Bibtex
@INPROCEEDINGS{2005-485-500-P, author = {E.P.K. Tsang and T. Gosling and B. Virginas and C. Voudouris and G. Owusu},
title = {Retractable Contract Network for Distributed Scheduling},
booktitle = {In proceedings of the 2nd Multidisciplinary International Conference on Scheduling : Theory and Applications (MISTA 2005), 18 -21 July 2005, New York, USA},
year = {2005},
editor = {G. Kendall and L. Lei and M. Pinedo},
pages = {485--500},
note = {Paper},
abstract = {This paper is about distributed scheduling where individual agents have potentially conflicting interests. It is motivated by BT’s workforce scheduling problem, where multiple service providers have to serve multiple service buyers. The service providers and buyers all attempt to maximize their own utility. The overall problem is a multi-objective optimization problem; for example, one has to maximize completion rates and service quality and minimize travelling distances. In this paper, BT’s problem is modelled as an open constraint optimization system. Standard contract net is a practical strategy in distributed scheduling where agents may have conflicting objectives. In this paper, we have introduced a retractable contract net protocol, which we call RECONNET, that supports hill-climbing in the space of solutions. It is built upon a job-release and compensation mechanism. RECONNET is a general protocol, which could be used to implement complex meta-heuristic algorithms such as Tabu Search and Guided Local Search. A system based on RECONNET has been implemented for BT’s workforce scheduling problem. The software, which we call ASMCR, allows the management to have full control over the company’s multiobjectives. The manager generates a Pareto set of solution by defining, for each buyer and seller, the weights given to each objective. ASMCR gives service buyers and sellers ownership of their problem and freedom to maximize their performance under the criteria defined by the management. ASMCR took 5 to 15 minutes to complete when tested on real-sized problems. It has potential to be developed into practical solutions to BT’s workforce scheduling problem.},
owner = {Faizah Hamdan},
timestamp = {2012.05.21},
webpdf = {2005-485-500-P.pdf} }