Cannot avoid penalty for fluctuating order arrival rate? Lets minimize Warehouse management system assigns a preferred completion time for every order based on the customer profile and the good(s) that isare ordered. Even though employing multirobot systems to manage goods movement bring operational efficiency in a warehouse, it is difficult to meet these soft deadlines of tasks in the peak hoursseasons. This can impact the respective businesses significantly as the lateness of task completion incurs a directindirect penalty. In this work, we develop an online task scheduling algorithm for such a multirobot system, called Online Minimum Penalty Scheduling (OMPS). Though there exists a large number of multirobot 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 nearoptimal online task schedule. By comparing with the stateoftheart 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 stateoftheart offline task scheduling algorithm.

Scheduling of Mobile Workstations for Overlapping Production Time and Delivery Time Many existing mobile service robots, including the robots in RobocupHome, perform their designated tasks only when the robots are stationary. The efficiency of these robots can be improved if they can perform some tasks while moving. In this paper, we propose the concept of mobile workstations, which combine mobile platforms with production machinery to increase efficiency by overlapping production time and delivery time. We present a model of mobile workstations and their jobs and describe the task planning algorithm for a team of mobile workstations. The temporal planning problem for mobile workstations combines both features of job shop scheduling problems (JSP) and traveling salesman problem (TSP), but there is little work in the literature that tackles both JSP and TSP simultaneously. Our first algorithm is a complete search algorithm which returns an optimal temporal plan with minimum makespan, and our second algorithm conducts a local search in the space of task graphs so as to quickly return suboptimal temporal plans. According to our experiments, when the number of jobs is small, our second algorithm can generate nearoptimal temporal plans, and when the number of jobs is large, our algorithm can generate much shorter plans than SGPlan 5 and a version of job shop scheduling algorithms.