A Single-Machine Scheduling Problem Modeling a Multiple Loan Repayment Problem

This paper discusses the problem of multiple loan repayment by formulating it as a single-machine scheduling problem. This problem arises when job processing times are variable and subject to change based on (repayments) due dates. The main objective is to minimize the time required to complete all jobs i.e. repay all the loans. Here, each job (loan) is completed independently and without interruption. This problem is challenging because there is a possibility of a job's processing time deteriorating over time. We proved that the general problem is NP-hard, give some polynomially solvable sub-problems and subsequently designed a MILP model to address it. However, due to the NP-hardness of this problem, we recommend using a heuristic and a genetic algorithm as well. We conducted computational experiments using randomly generated test instances to validate our approach. Our findings indicate that the model can produce better solutions for up to 40 jobs within one hour time frame. Additionally, the genetic algorithm performs well compared to the heuristic for larger instances.