Genetic Programming for Auction Based Scheduling


Bader-El-Den M., Fatima S.

13th European Conference on Genetic Programming, İstanbul, Turkey, 7 - 09 April 2010, vol.6021, pp.256-267 identifier

  • Publication Type: Conference Paper / Full Text
  • Volume: 6021
  • City: İstanbul
  • Country: Turkey
  • Page Numbers: pp.256-267

Abstract

In this paper, we present a genetic programming (GP) framework for evolving agent's binding function (GPAuc) in a resource allocation problem. The framework is tested on the exam timetabling problem (ETP). There is a set of exams, which have to be assigned to a predefined set of slots and rooms. Here, the exam time tabling system is the seller that auctions a set of slots. The exams are viewed as the bidding, agents in need of slots. The problem is then to find a schedule (i.e., a slot for each exam) such that the total cost of conducting the exams as per the schedule is minimised. In order to arrive at such a schedule, we need to find the bidders optimal bids. This is done using genetic programming. The effectiveness of GPAuc is demonstrated experimentally by comparing it with some existing benchmarks for exam timetabling.