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: jkassu@gmail.com, berhan.eshetie@gmail.com 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. # II. # Literature Review 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. # a) Model Representation and algorithm 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]. # III. # Results and Discussions 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 Jobs Precedence constraints J1 M1(2) M2(2) M3(5) M4(2) M5(3) J2 M1(2) M3(2) M4(1) M2(2) M5(2) J3 M1(2) M4(2) M3(3) M2(2) M5(3) J4 M1(1) M2(2) M3(2) M4(1) M5(2) J5 M1(2) M3(2) M4(2) M2(2) M5(3) 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. DAVI production system using shifting bottleneck algorithm.Year 201521XV Issue I Version I( ) Volume Jof Researches in EngineeringGlobal Journaloperations (Oi1, Oi2..., Oim), where Oik (the k th operation I © 2015 Global Journals Inc. (US) of 21. initialize2. M o = ø (scheduled machines)3. G= only conjunctives arcs4. G max = critical path in G5. Choose a machine Mi;6. for each machine M i Ñ?" {M-M 0 }Generate the 1|r j |L max scheduleCompute L max (i)7. Scheduling the bottleneck machine? Let k be the machine that minimizes L max (i)? Schedule k by the 1|r j |L max solution? Update G? Mo= Mo ?{k}8. Re-Sequence already scheduled machines9. For each Mi ? M0? {k}doDelete disjunctive arcs for Mi from GForm the 1|rj|LmaxReschedule M i according to this schedule10. WhileM = M 0 stop,else go to 2 © 2015 Global Journals Inc. (US) ## Conclusion Job-shop scheduling is an NP-complete combinatorial optimization problems which comprises m machine and n jobs. This research paper aims at scheduling of 5-machines and 5-jobs using shifting bottleneck heuristic algorithm methods built-in-heuristic Lekin scheduling software based on secondary data collected from DAVI production system. The findings of the study showed that the SBH resulted in a total makespan of 22 hours with 8.33% improvement as compared to the current scheduling system that DAVI operates in its production line. The percentage utilization of machines shows that machine three is the busiest machine whereas machine one and four have relatively the lowest percentage utilization which is less than 50%. * Performance of decomposition procedures for job shop scheduling problems with bottleneck machines RehaUzsoy & Cheng-ShuoWang 10.1080/002075400188843 International Journal of Production Research 38 6 2000 * A computational study of a shifting bottleneck heuristic for multi-product complex job shops, Production Planning & Control: The Management of Operations LarsMönch & JensZimmermann 10.1080/09537287.2010.490015 2011 22 * Comparison of Jssp Based Genetic Algorithm with Benchmark Problems for Optimality ALKameswari 1 & K. Sreenivasa Rao International Journal of Mathematics and Computer Applications Research Issn 2249-6955 2 2012 Ijmcar * Guided local search with shifting bottleneck for job shop scheduling EBalas AVazacopoulos 1994 Pittsburgh GSIA Carnegie Mellon University Tech. Rep.,ManagementScience-ResearchReportMSRR-609 * Mathematical optimization of a flexible job shop problem including preventive maintenance and availability of fixtures KarinThörnblad * EASilver DFPyke RPeterson Inventory Management and Production Planning and Scheduling Management USA John Wiley & sons 1998 * Review on Job-Shop and Flow-Shop Scheduling using Multi Criteria Decision Making *Sultana Parveen HafizUllah Transaction of the Mech. Eng. Div 41 2 2010 The Institution of Engineers * Cultural algorithms, an alternative heuristic to solve the job shop scheduling problem, Engineering Optimization RicardoLandaDaniel Cortés Rivera ABecerra & Carlos Coello Coello 10.1080/03052150600956811 2007 39 * Modified bottleneck -based heuristic for large scale job-shop based scheduling problem with single bottleneck ZuoYan GUHangu XIYugeng journal of system engineering and electronics 18 3 2007 * propose a modified shifting bottleneck procedure for job shop scheduling" college of computer science and technology ZhiHuang P.R. china Huazhong Universtiy of Science and Technolgy Wuhan * A heuristic algorithm for the m-machine, n-job flow shop sequencing problem MNawaz EEEnscore IHam OMEGA 11 1983 * Factory Physics Foundation of Manufacturing Management WJHopp MLSpareman 2001 McGraw-Hill Singapore * Production and Operation Management RPanneerselvam 2006 Prentice Hall New Delhi, India * Mathematical models for job-shop scheduling problems with routing and process plan flexibility CemalÖzgüven LaleÖzbak?r YaseminYavuz Applied Mathematical Modelling 34 2010. 2010 * MPinedo Scheduling: Theory, Algorithms, and Systems New York Prentice-Hall 2001 * Introduction to Sequencing and Scheduling KRBaker 1974 Wiley and Sons New York