1.

Introduction n today's competitive markets, manufacturers have to respond quickly to orders and meet shipping dates promised to the customers, as failure to do so, at least, may result in a significant loss of good will [1]. Among many techniques that makes manufacturers competent in the business arena scheduling is one of the operation to accomplish activities on time and deliver products in their lead time. Customer satisfaction is the last outcome of organizations. This requires an optimum scheduling system that allocate scares resources.

Scheduling is the allocation of shared resources over time to competing activities to satisfy customers' requirement. It has been the subject of a significant amount of literature in the field of operations research. Emphasis has also been given on investigating machine scheduling problems where jobs represent activities and machines represent resources so that each machine can process at most one job at a time [1,2].

Machine scheduling is viewed as a dynamic problem usually an NP-complete combiner's in the production scheduling problems [3,4,5,1,2,6,7,8]. After a job is processed in a particular machine, the condition of the jobs waiting to be processed on the same machine may be changed due to any of several reasons. For example, new jobs may arrive or the remaining slack times or may be changed even though Author ? ?: Addis Ababa University, Addis Ababa Institute of Technology, Addis Ababa, Ethiopia. e-mails: [email protected], [email protected] no job arrives during the processing time of the previous job on the machine [8,9]. Therefore, it requires a rescheduling effort to determine which job to be processed next.

Scheduling is a multifaceted in nature and it consumes large resource. Even for small problems, there is absolutely no guarantee that an optimal final solution can easily be obtained. To this effect, heuristic approach have been used by researchers.

Shifting bottle neck heuristics (SBH) is one of the procedures intend to minimize the makespan in a job shop. It follows that in the pre-defined machines sequence there is always one machine with bottleneck in the processing sequences. This heuristic algorithm tries to minimize the effect of the bottleneck process through iterative method in finding maximum makespan (C max ) and maximum lateness time (L max ).

Dejena Aviation Industry (DAVI) which is a job shop manufacturing company in Ethiopia faced similar problem in its production system. It experiences a longer makespan in its production system. Therefore the objective of this study is to minimize the makespan of DAVI using shifting bottleneck heuristic algorithm.

Many literatures conducted regarding scheduling, job shop, and shifting bottleneck in the manufacturing systems of a job shop production system. Scheduling is defined as "It is to forecast the processing of a work by assigning resources to tasks and fixing their start times" as defined by [24,25,26]. Job shop scheduling is a work location in which a number of general purpose work station exist and are used to perform a variety of jobs such as a traditional machine shop with similar machines type located together, batch or individual production.

The job shop problem studied in the present paper consists in scheduling a set of jobs on a set of machines with the objective to minimize the makespan, i.e., the maximum of completion times needed for processing all jobs, subject to the constraints that each job has a specified processing order through the machines and that each machine can process at most one job at a time [10].

In the job shop scheduling problem (JSP), there are n jobs that must be processed on a group of m machines. Each job i consists of a sequence of m The job shop scheduling problem, which is among the hardest combinatorial optimization problems that is strongly NP-complete [11]. During the past decades, many researchers have been focusing on the problem and proposed several effective algorithms for it. These algorithms can be classified as optimization and approximation algorithms. The optimization algorithms, mostly used, are based on the branch and bound scheme [11]. These algorithms have made considerable achievement, however, their implementation needs too much computational cost. On the other hand, approximation algorithms, which are more effective for large size problem instances, use several approaches classified as: (a) local search, (b) dispatching priority rules, (c) shifting bottleneck approach, (d) stimulated annealing, and (e) tabu search [11].

Various scholars have been used different approach to solve job shop scheduling problem. Among the many researchers one, Katuri propose Optimization of job shop scheduling using shifting bottle neck technique to reduce total flow time of job shop scheduling problem and arrive the optimal solution [12]. Kai-Pei Chen (2007) proposes an assembly job shop scheduling problem with component availability constraints, a modified disjunctive graph formulation. Also he developed a mixed integer programming model with objective of minimizing the total weight tardiness [13]. Zhi Huang propose a modified shifting bottleneck procedure for job shop scheduling with objective to minimize the make span. In this study dispatching and heuristic approach was used due to the job shop operation practice of the case company.

Generally, JSP uses various representation in its model. In this project let a job shop consists of a set of Mj machines where j=1, 2... m, n jobs, and a predefined plan which states the assignments of these jobs in different machines in some desired sequences (constraints). Each job has a specified number of operations to be carried out in different machines, with individual setup times, processing times, a due date, etc. The job shop sequencing problem deals with the study of an optimal sequencing of the operations (of the jobs) in different machines within the specified constraint requirements [14].

A job-shop does not have the same restriction on workflow as a flow-shop. In a job-shop, jobs can be processed on machines in any order. The usual job shop, from a research standpoint, is one in which there are m machines and n jobs to be processed. Each job requires m operations, one on each machine, in a specific order, but the order can be different for each job [15,16].

The shifting bottleneck heuristic is an efficient method to find C max and L max objectives in a job shop [13] with an iterative method. At each iteration of the method, a bottleneck machine was identified using 1 /r j / L max approach. A processing sequence of job on the machine bottleneck machine was found so as to minimize L max [13]. The shifting bottleneck algorithm used in this paper is represented as follow: and continue the same iteration until optimum solution is obtained [1,2,6,7,8,9,17].

In this study, the jobs selected from list of spare parts manufactured in DAVI which covering 8% of job orders. The data was collected from jobs: spur gear (J 1 ), shaft with key (J 2 ), adapter (J 3 ), flange (J 4 ) and fitting (J 5 ). These jobs were processed by machines namely power hack saw (M 1 ), lathe machine (M 2 ), milling machine (M 3 ), drilling machine (M 4 ) and grinding machine (M 5 ). The precedence matrix constraint contains for all selected jobs only and machines are presented in Table 1.

Table 1 : Routing matrix the five jobs and five machines

Once the precedence constraint development of the jobs on each machine were developed by considering machining operation requirements as shown Table 1 and setting all the parameters, Lekin scheduling software were used to find the optimum sequences of operations. The findings of the research result with shifting bottleneck heuristic is shown in Table 2 and gnat chart for optimum job sequence is shown in Figure 1. There are methods that are built-in-heuristics in minimizing flow times of job shop scheduling. These are: a) Shifting bottleneck heuristics b) Local search heuristic c) Hybrid methods Here in this study shifting bottlenech heuristic has been considered with its three policies/options. The following three policies/options has been utilized in Table 2 resulting in performance measurement of the case.

? General SB Routine (most objectives)

? Objective Specific routines: SB/sumwT (Total Weighted Tardiness) and

? Objective Specific routines: SB/Tmax (Maximum Tardiness, Makespan)

The key performance measurements are define below. From Table 2 and Figure 1, the findings of the simulation run show that the shifting bottleneck heuristic with the option of shifting bottleneck sum weighted tardiness approach resulted in a minimum makespan of 22 hours with job sequences of job 4-2-5-3-1. The optimum sequence has improved the makespan of DAVI by an 8.33%. In this sequence the operation started on machine one with job 4 and ends on machine five with job one. The findings of the study also showed that the percentage utilization of each machine. Accordingly, the percentage utilization of machine one is 40.91%, machine two 45.54%, machine three 63.63%, machine four 36.4% and that of machine five 59.09% of their available time.