Scheduling can be described as “the allocation of scarce resources over time to perform a collection of tasks”. They arise in many practical applications in manufacturing, marketing, service industries and within the operating systems of computers. Scheduling problems are frequently encountered in various activities of every day life. They exist whenever there is a choice o f the order in which a number of tasks can be performed Some examples are scheduling of classes in academic institutions, jobs in manufacturing plants, patients on test facilities in health institutions and programs to be run at a computing centre. The desire to perfoim the tasks in a special order to achieve some objective is what makes scheduling problems important. In this thesis we will use the machine shop terminology, even though the actual situations that give rise to scheduling problems are wide and varied. Since a complete description of a real machine shop would be too detailed to serve as a conceptual basis for any meaningful analysis, we will adopt a simplified model consisting of a job shop and a despatch area through which jobs are received from outside and then passed to the job shop. Such a model can adequately reflect the aspects of real machine shops that are important for predicting performance. The performance of such a job shop system models is normally measured by either the production capacity or mean tardiness or the mean number in the system, in the job shop and in the despatch area. Scheduling problems differ in: • input, the manner in which the jobs arrive at the system • despatch policy, the policy by which the jobs are despatched to the shop, and • routing, the order in which the jobs go from one machine centre to the other in the job shop