A Market-Based Scheduling Mechanism Design for Cost Reduction in Home Health Care

We consider a decentralized home health care scheduling setting where a health care agency assigns a group of independent health care practitioners to home visits. Health care agency's objective is to minimize the overall payments for covering all planned visits, while a practitioner's cost is considered as his/her private information unknown to the agency. The key challenge here is how to allocate home visits to practitioners such that high quality solutions, which benefit both the health care agency and the practitioners can be obtained. To tackle this challenge, we design a market-based mechanism in the format of an iterative auction which enables the computation of cost effective schedules through multilateral negotiation among the health care agency and practitioners. The effectiveness of the designed mechanism is evaluated through a computational study conducted in a proof of concept prototype environment. Our experiment results show that the designed scheduling mechanism achieves on average 96% efficiency compared with the optimal solutions. In addition to experiment results, we prove that the mechanism can always compute optimal solutions to a special case of the home health care scheduling problem.