Chapter-2 Literature Review

CHAPTER -2 LITERATURE REVIEW Like many operation research (OR) application areas the study of the scheduling theory began in the early 1950’s. Johnson’s article is acknowledged as a pioneering work. Later, several kinds of general optimization procedures were applied to scheduling problems. These included mixed and pure integer programming formulations, dynamic programming and branch and bound methods. Meanwhile, heuristic methods were being developed for problems which were known to be computationally difficult. By the late 1960’s, a solid body of scheduling theory had emerged. In 1970’s theoretical work on problem complexity began. It was found that most problems are NP-hard. The last decade has seen the tendency to emphasize the practical nature of scheduling problem and to try to bridge the gap between theory and practice. Blackstone et al. [2] defined Scheduling rules as: ‘rules used to select the next job to process from jobs waiting for service’. Scheduling rules can be very simple or extremely complex. Examples of simple rules are: ‘select a job at random’, or select the job that has been waiting longest’. A more complex rule might be one that selects the job with the ‘closest due date whose customer’s inventory is less than a specified amount’. Pierreval, H., and Mebarki, N., [7], Blackstone et al. [2], Baker [1], Ramasesh [9] have dealt with many scheduling rules. A universally well accepted result of these studies is that no scheduling rule performs globally better than any others. The scheduling rule’s performance depends on the configuration of the studied system, the operating conditions and the performance criterion used to evaluate the scheduling rules. As a consequence, decision makers often have difficulty in selecting the scheduling rules that are the most suited to their problems. This has led several researchers to propose various methods for selecting the scheduling rules best suited to given cases.

7

Haupt, R [4] classified Scheduling or Dispatching rules as:  Process-time based rules  Due-date based rules  Combination rules and  Rules that are neither process-time based nor due-date based. The shortest processing time (SPT) rule is an example of a process-time based rule. The process-time based rules ignore the due-date information on jobs. Due-date based rules schedule the jobs based on their due-date information. An example of a due-date based rule is the earliest due-date (EDD) rule. Blackstone, J.H. et al [2] proposed Combination rules which make use of both process-time and due-date information, e.g. Least Slack rule, Critical Ratio, etc. Haupt, R [4] proposed the rules which do not fall into any of the above categories and loads the jobs depending on shop floor conditions rather than on the characteristics of jobs. An example of this type of rule is the WINQ rule (total work-content of jobs in the queue for the next operation on a job). Conway et al. [3] gave a general notation scheme for scheduling problems based on four descriptors A/B/C/D which has since been followed by a number of researchers. Representation of scheduling problems is as follows  A- Number of jobs

(any positive integer, usually ‘n’)

 B- Number of machines (any positive integer, frequently ‘m’)  C- Flow pattern and further technological and management constraints. Possible values are:  ||: single machine  ‘J’: job shop  ‘F’: flow shop  ‘O’: open shop  F-perm: permutation flow shop  k-parallel: k-machines in parallel  J, k-parallel: job shop with k parallel machines at each stage

8

 D- Criteria to be optimized. A range of methods have been developed to solve the scheduling problems which are classified as follows.  Scheduling rules and simulation  Mathematical programming formulation and solution (Branch and bound techniques, Dynamic programming)  Artificial Intelligence techniques (Expert systems and Knowledge based systems)  Heuristic search methods (Tabu search, Simulated annealing, Genetic algorithms) While the use of heuristic algorithms is mostly resorted to in the case of static scheduling problems, scheduling rules are made use of in the case of dynamic scheduling problems. Scheduling rules are more popular in many real life manufacturing systems than heuristics, mainly because scheduling rules are simple to implement and use in any shop floor, and most real-life systems have dynamic arrivals. These rules some times called dispatching rules or priority rules have led to a substantial amount of research in the last few decades, especially to solve the dynamic scheduling problem of job shop systems.

9