This paper proposes an improved algorithm for the multiprocessor job scheduling problem based on First-Come-First-Served (FCFS) strategy. Depending on the job processing times, some jobs are divided into multithreads while others remain as single thread jobs. Multithread jobs are processed based on the concept of gang scheduling. Backfilling technique is used to improve the performance of the proposed algorithm. The results of the proposed algorithm are presented using a percentage gap from a lower bound.

Job scheduling is of utmost importance due to the demands of the massively parallel computers existing today. It has become extremely difficult to construct algorithms which are optimal. Only approximate methods are available which are far from satisfactory in many situations.

First-Come-First-Served (FCFS) is a simple, straightforward scheduling approach which can be found in many real systems. In the FCFS approach no priority is given to any job, but a queue of jobs is formed and they will be processed according the position of a job in the queue.

Uwe and Ramin (1998a), in their analysis of FCFS parallel job scheduling, showed that for many work loads good performance can be expected from an FCFS job schedule. One of the main issues related to this approach is the presence of idle times in the processors. A scheme which minimizes the idle times will give rise to better solutions. However, the method of doing this is not clear even though several studies exist which attempt to do so. One of the drawbacks of these studies is the absence of methods which could compare the solutions obtained with the optimal solutions in relevant situations. As a result, it is not possible to find how far the solution lies from the optimal. Various modifications to FCFS approach have been proposed in the literature. Uwe and Ramin (1998b) proposed a method emphasizing the notion of fairness. This method has incorporated the idea of preemption of jobs. Preemption is a technique in which a currently running job is interrupted in favor of a high priority job.

In this paper, we propose an improvement to FCFS approach which reduces idle times by bringing some jobs to the front by relaxing the requirement of FCFS order. This is known as backfilling (Feitelson et al., 2004). At the same time, we also compare the solutions we obtained by running the same set of problems with the FCFS approach. By doing so, we hope to give some idea about the quality of solutions obtained for a set of test problems.

Computer Sciences Journal, Business Intelligence, Enterprise Systems, Enterprise Resource Planning, Customer Relationship Management, CRM, Business Operations Management, Business Process Mining, Finite State Machine, Transactional Information System, Genetic Algorithms, Decision Making Process, Data Mining Tools, Online Analysis Processing, OLAP, Artificial Intelligence.