الفهرس | Only 14 pages are availabe for public view |
Abstract Capacity planning of multi-item products in make to order industries represents one of the major problems that faces the management. Many efforts have been devoted to schedule several jobs on several machines. Some of these efforts were successful in obtaining schedules which yield near optimal make spans. However most of the efforts were devoted to solve the problems of single item products without any consideration to constraints imposed by the limited production capacity. The objective of the present work is to device a heuristic algorithm capable of handling capacitated scheduling problems of multi-item products on several production facilities. The following are the different techniques used and developed in that concern: 1. SELECTED SINGLE ITEM JOBS SCHEDULING ALGORITHMS: Ignall & Schrage algorithm which is based on branch and bound technique and the CDS algorithm which is based on Johnson’s algorithm, are known to posses the highest efficiency in solving single item scheduling problems compared to other available algorithms. For that reason, they were chosen for investigation for further development and comparison purposes with the heuristic algorithms to be developed in the present work. They were applied on several case studies to study the effect of different factors which may affect the efficiency of the algorithms. Computer programs were developed for these algorithms to solve the flow shop single item jobs scheduling problems. 2. DEVELOPED ALGORITHMS FOR SINGLE ITEM JOBS SCHEDULING: The aim of the developed algorithms in the present work is to obtain better results compared to that of other researchers algorithms. Two algorithms, based on the Branch and Bound concept, were developed to schedule a number of single item jobs on several machines. The algorithms depends on composing an initial sequence and then obtain other possible sequences by applying the branching concept. By applying the sequence generation rule, a number of branches sprout and end with the job processing sequences. Further branching can be made at any node in the generated sequences tree. The different generated sequences at any node are determined by placing any of the unscheduled jobs to succeed the last scheduled job in the node sequence. The make span is then calculated for each sequence at each node. The node at which the sequence of jobs gives the minimum make span is chosen for further branching. Selection of nodes and subsequent branching is continued until no improvement in the total make span is achieved and therefore, a solution is obtained. The developed algorithms differs only in the way of arranging the initial sequence. In the first algorithm (TWC) the initial sequence is made by arranging the jobs in descending order according to their total work content. The second algorithm (DISH) depends on considering the sequence resulted from Ignall and Schrage algorithm as an initial sequence. The DISH algorithm IS an improvement to the schedule resulted from Ignall and Schrage algorithm. 3. DEVELOPED HEURISTIC ALGORITHM TO SOLVE CAPACITATED SCHEDULING PROBLEMS OF MULTI-ITEM PRODUCTS: The aforementioned developed algorithms were extended to solve capacitated scheduling problems of multi-item products. Also, Ignall and Schrage algorithm was extended to solve the same type of problem. The solution algorithm was made using matrices arrangements throughout the whole procedure were matrix algebra was applied to reach the solution. The algorithm was made to satisfy the precedence constraints by following the Gozinto representation and product explosion model following Vazsonyi model. The capacitated schedule was made by following a bidding concept to decide upon the jobs in sequence among the candidated jobs. Several examples had been proposed to test the sensitivity and compare between the results obtained from each. The examples were randomly generated covering the factors affecting the problem as number of products, number of machines, number of levels in multi item products. Also, some of the examples were specially designed to experience odd cases. For single jobs scheduling, the results obtained from applying the developed heuristic algorithms were found to be superior in comparison with the results of other researchers even for small size problems. The present algorithms yielded the optimal solutions in most of small size cases where other algorithms failed. Optimal solutions were determined by applying complete enumeration of different sequences for a maximum of seven products . |