A Mixed Integer Linear Programming Model for Real-Time Task Scheduling in Multiprocessor Computer System

Abstract

There has been an upsurge in real-time multimedia applications in recent time. On a network, the ability of an average uniprocessor computer to handle such data may be limited due to the large size of such data. Also, there may be a high number of concurrent users who may want to retrieve data and the need to process them in real-time; and in continuous stream. This may lead to low quality service and deadline misses. The advent of multi-processor systems offers a more efficient way of processing multimedia data in real-time. With the development of appropriate scheduling algorithm, another challenge is the mode of assigning tasks in multi-processor systems. This calls for the use of an appropriate mathematical model that will take cognizance of the nature of variables involved. In this research work, a Mixed Integer Linear Programming Model (MILP) was developed to assign tasks in a multiprocessor system. The MILP model was used to assign tasks to multi-processor systems ranging between 5 and 10 homogenous processors. The result of the simulation runs shows that with the appropriate scheduling algorithm, a high success rate ratio and guaranteed number of deadlines met could be achieved.