Academic Journals Database
Disseminating quality controlled scientific knowledge

Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines

Author(s): Panneerselvam Senthilkumar | Sockalingam Narayanan

Journal: Intelligent Information Management
ISSN 2160-5912

Volume: 02;
Issue: 08;
Start page: 457;
Date: 2010;
Original page

Keywords: Uniform Parallel Machines | Measure of Performance | Heuristic | Model | Competitive Ratio

This paper presents a survey of single machine scheduling problem with uniform parallel machines. The single machine scheduling problem with uniform parallel machines consists of n jobs, each with single operation, which are to be scheduled on m parallel machines with different speeds. These parallel machines are also called proportional machines or related machines. There are several measures of performance which are to be optimized in uniform parallel machines scheduling. Since, this scheduling problem is a combinatorial problem; usage of a heuristic is inevitable to obtain solution in polynomial time. This paper gives a classification of the literatures of this scheduling problem in three major categories, viz. offline scheduling, online scheduling and miscellaneous scheduling. In total, the available literatures are classified into 17 subgroups. Under each of the first two categories, the available literatures are discussed under different groups based on different measures of performance and non-preemptive/preemptive nature of the jobs. In the last category, the literatures are discussed under three subgroups, namely non-preemptive jobs, preemptive jobs and periodic jobs.
Why do you need a reservation system?      Affiliate Program