Constraint-based winner determination for auction-based scheduling

This paper presents a formulation and an algorithm for the winner determination problem in auction-based scheduling. Without imposing a time line discretization, the proposed approach allows bidders to bid for the processing of a set of jobs under scheduling constraints using a requirement-based bidding language. The proposed winner determination algorithm uses a depth first branch and bound search. The search branches on bids and a constraint directed scheduling procedure is used at each node to verify the feasibility of the temporary schedule. The performance of the proposed algorithm is evaluated through experiments versus a set of auction-based scheduling winner determination problems generated based on a suite of job shop constraint satisfaction benchmark problems from the literature. Experimental results show that the proposed algorithm is on average more than an order of magnitude faster than the commercial optimization package CPLEX 10.0 over the tested problem sets.Cet article pr\ue9sente une formulation et un algorithme en vue de la r\ue9solution du probl\ue8me de d\ue9termination du gagnant dans un ordonnancement de type par ench\ue8res. Sans imposer une discr\ue9tisation des lignes temporelles, l?approche propos\ue9e permet aux soumissionnaires de soumissionner en vue du traitement d?un ensemble de travaux assujettis \ue0 des contraintes d?ordonnancement au moyen d?un langage de soumission fond\ue9 sur les exigences. L?algorithme propos\ue9 de d\ue9termination du gagnant utilise une recherche par s\ue9paration et \ue9valuation en profondeur d?abord. L?algorithme s\ue9pare les soumissions et utilise \ue0 chaque n?ud une proc\ue9dure d?ordonnancement en fonction des contraintes pour v\ue9rifier la faisabilit\ue9 du calendrier temporaire. L?ex\ue9cution de l?algorithme propos\ue9 est \ue9valu\ue9e au moyen d?exp\ue9rimentations pour un ensemble de probl\ue8mes de d\ue9termination du gagnant, dans un ordonnancement par ench\ue8res, g\ue9n\ue9r\ue9s en fonction d?une suite de probl\ue8mes d?\ue9valuation de la satisfaction des contraintes de travail \ue0 fa\ue7on tir\ue9s de la litt\ue9rature. Les r\ue9sultats d?exp\ue9rimentation montrent que l?algorithme propos\ue9 est en moyenne plus rapide que le progiciel d?optimisation commercial CPLEX 10.0 de plus d?un ordre de grandeur, pour les ensembles de probl\ue8mes test\ue9s.Peer reviewed: YesNRC publication: Ye