Cannot avoid penalty for fluctuating order arrival rate? Let's minimize

摘要

Warehouse management system assigns a preferred completion time for every order based on the customer profile and the good(s) that is/are ordered. Even though employing multi-robot systems to manage goods movement bring operational efficiency in a warehouse, it is difficult to meet these soft deadlines of tasks in the peak hours/seasons. This can impact the respective businesses significantly as the lateness of task completion incurs a direct/indirect penalty. In this work, we develop an online task scheduling algorithm for such a multi-robot system, called Online Minimum Penalty Scheduling (OMPS). Though there exists a large number of multi-robot task scheduling algorithms, they are not suitable (or less efficient) for a system where each task has a soft deadline and accumulates penalty if it is executed beyond its deadline. Moreover, the lack of knowledge of future tasks (online scheduling) makes task allocation a much more difficult job. OMPS provides a robust, scalable, and near-optimal online task schedule. By comparing with the state-of-the-art algorithm, we show that OMPS attracts up to 78% less penalty when a significant number of tasks are bound to miss the deadline. Additionally, it achieves a competitive ratio of up to 1 when compared with a state-of-the-art offline task scheduling algorithm.