Grant: Discovery Grants Program - Individual

Canada's rapidly aging population is placing ever increasing demands on limited health care services, especially in more remote regions of the country. Optimized scheduling is the only way to meet this challenge. Consider the services available in health care. Each service has a limited number of available time slots. These time slots are posted on a website and a group email is sent to all outpatients. The email directs these individuals to indicate their service requirements by using the website. Outpatients as bidders express their requests as bundles of service time slots. Each bundle consists of several subsequent time slots. Each outpatient has a priority value assigned by his/her family doctor to indicate the level of urgency relative to all patients. In fact, the priority value is similar to the price a bidder is willing to pay in an auction. To bid for time slots, each outpatient must consider special constraints relative to his/her needs, e.g., length of the bundles, number of slots, and preferences. Request collection will be closed at the expiration time indicated in the email. The scheduling program is then activated, its goal being optimization of the whole prices (priority values) by assigning time slots to outpatients relative to their constraints. This is in fact a kind of Winner Determination Problem (WDP) that is NP-hard (non-deterministic polynomial-time hard). After the program obtains the result, a new schedule is communicated to the outpatients. This research is aimed to 1) provide a Web-based platform (including a website and all the developed optimization codes) for the outpatient bidding process; and 2) introduce heuristics to improve the efficiency of algorithms for auction-based scheduling problems with the intent of creating acceptable near optimization results. A solid foundation for this proposed research is established by results from the applicant's previous NSERC research on Role-Based Collaboration (RBC), i.e., Group Role Assignment Problems (GRAPs), which have been formalized and solved through development of efficient algorithms.