The multiple-job repair kit problem
The repair kit problem is that of finding the optimal set of parts in the kit of a repairman. An important aspect of this problem, in many real-life situations, is that several job-sites are visited before a kit is restocked. In this paper, we present two heuristics for solving the multiple-job repair kit problem. Both heuristics can be used to determine a solution under the service-objective (minimal holding cost for a required job-fill rate) as well as the cost-objective (minimal expected total cost, including a penalty cost for each broken job). They generate a series of kits from empty to complete by adding one part at a time, and then select the kit with the smallest (approximate) total cost. The Job Heuristic (JH) adds parts based on the ratio of holding cost to increase in job-fill rate, whereas the Part Heuristic (PH) focuses on the ratio of holding cost to increase in the part-fill rate. Since part-fill rates are much easier to calculate, the PH is easier to apply. In fact, we show how it can be applied in a spreadsheet software package. The JH, however, is more exact. Indeed, it determines the optimal solution for all the examples (for which we are able to determine the optimal solution by complete search) considered in our numerical experiments. The PH also performs well. It generally has a cost error of less than 2% and determines the optimal solution in most cases, even if part failures are highly dependent. Based on these results, we recommend the use of the PH in practice.
repair kit problem heuristics multiple jobs