A cellular neural network based analog computing approach for ultra-fast adaptive scheduling
Venkata Sai Dattu Potapragada · 2009
Scheduling is the process of allocating resources to the tasks over time. A scheduling problem can be modeled as an assignment problem under constraints and is therefore an optimization problem. In real scenarios a scheduling problem is dynamic in nature as the information required is often gradually revealed or changes over time. In the case of dynamic problems, planning is performed in real time and the related scheduling must be finished before the time window reaches the deadline. The major factors that make the scheduling problems dynamic are: • The dynamic nature of tasks: inclusion of new tasks at run-time or the exclusion of some existing tasks results in a need for a rescheduling. • Random failures: equipment failures result in unpredicted process flows; this generally requires a rescheduling. • Sequence-dependent setups: makes each job to wait for its time and sometimes delayed because of the eventual unavailability of resources. Traditional scheduling techniques face a serious complexity problem due to the NPhard nature of the related optimization problem. Therefore, a key challenge is the search for algorithms/schemes which should provide good quality solutions but at a computation time fitting the requirements of a real-time computing. The so-called “analog computing” is considered in this work to design a novel scheme capable of delivering an optimal solution of the scheduling problem at a relatively ultra-short time while compared to traditional counterparts’ like approaches involving operations research schemes or heuristics. The novel scheme will involve, in the heart, cellular neural networks (CNN) based processors, which will be the key pillar of the analog computing based ultra-fast solver of the dynamic scheduling problems of relevance in transportation and production. CNN-based analog computing has the very interesting advantage of an easy implementation or emulation on digital platforms (i.e., on personal computers or on hardware platforms such as DSP and FPGA boards).