Co-evolutionary hyper-heuristic method for auction based scheduling

In this paper, we present a co-evolutionary hyper-heuristic method for solving a sequential auction based resource allocation problem. The method combines genetic programming (GP) for evolving agent´s bidding functions for the individual auctions with genetic algorithms (GAs) for evolving an optimal ordering for auctions. The framework is evaluated in the context of the exam timetabling problem (ETTP). In this problem, there is a set of exams, which have to be assigned to a predefined set of slots. Here, the exam time tabling system is the seller that sells a set of slots in a series of auctions. There is one auction for each slot. 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 find the bidders optimal bids for an auction using GP. We combine this with a GA that finds an optimal ordering for conducting the auctions. The effectiveness of this co-evolutionary method is demonstrated experimentally by comparing it with some existing benchmarks for exam timetabling.