In this paper we look at the problem of scheduling tasks on a single-processor system, where each task requires unit time and must be scheduled within a certain time window, and each task can be added to or removed from the system at any time. On each operation, the system is allowed to reschedule any tasks, but the goal is to minimize the number of rescheduled tasks. Our main result is an allocator that maintains a valid schedule for all tasks in the system if their time windows have constant size and reschedules O(1 *log(1 )) tasks on each insertion as ->0, where is a certain measure of the schedule flexibility of the system. We also show that it is optimal for any allocator that works on arbitrary instances. We also briefly mention a few variants of the problem, such as if the tasks have time windows of difference sizes, for which we have an allocator that we conjecture reschedules only 1 task on each insertion if the schedule flexibility remains above a certain threshold.
Of the wide variety of scheduling problems, completely offline problems from real-world situations tend to be NP-complete even after simplifications. (, 2008) @cite_12 But practical scheduling problems usually involve continuous processes or continual requests, and hence many other scheduling problems are online in some sense. In addition, scheduling problems with intrinsic constraints invariably have to include some means of handling conflicting requests.
@cite_12
2137527671
Uncertainty is a very important concern in production scheduling since it can cause infeasibilities and production disturbances. Thus scheduling under uncertainty has received a lot of attention in the open literature in recent years from chemical engineering and operations research communities. The purpose of this paper is to review the main methodologies that have been developed to address the problem of uncertainty in production scheduling as well as to identify the main challenges in this area. The uncertainties in process scheduling are first analyzed, and the different mathematical approaches that exist to describe process uncertainties are classified. Based on the different descriptions for the uncertainties, alternative scheduling approaches and relevant optimization models are reviewed and discussed. Further research challenges in the field of process scheduling under uncertainty are identified and some new ideas are discussed.