Proceedings:
Proceedings of the International Symposium on Combinatorial Search, 12
Volume
Issue:
Vol. 12 No. 1 (2019): Twelfth Annual Symposium on Combinatorial Search
Track:
Extended Abstracts
Downloads:
Abstract:
Most real-world project have a deadline and consist of completing tasks. In our setting, each task needs to be executed by a single supplier, chosen from a subset of suppliers that have the required proficiency to handle that task. The suppliers differ in their execution times, which are stochastically taken from known distributions. The Supplier Assignment for Meeting a Deadline (SAMD) problem is the problem of assigning a supplier to each task in a manner that maximizes the chance to meet the overall project deadline. We propose an A*-based approach, along with an efficient admissible heuristic function, that guarantees an optimal solution for this problem. Experimentally, we compare our A*-based approach to an exhaustive brute-force approach and several heuristic methods. The results show that our A*-based approach compares favorably with the heuristic methods, and is orders of magnitude faster than the exhaustive alternative.
DOI:
10.1609/socs.v10i1.18475
SOCS
Vol. 12 No. 1 (2019): Twelfth Annual Symposium on Combinatorial Search