Optimisation Of Job Shop Scheduling Problem For Batch Production

Optimisation Of Job Shop Scheduling Problem For Batch Production

Katuru Phani Raja Kumar 1, Dr. V Kamala 2, Dr. ACS Kumar 3

1*Research Scholar, JNTU Hyderabad.

2Professor, Mechanical Engineering TKR College Engg & Technology Meerpet Hyderabad

3Professor, Mechanical Engineering JNTUH (Rtd) Hyderabad

Abstract

The Job Shop Scheduling is a major aspect, for which maximum utilization of the resources have to be considered. Each job has a constrained sequence of operations which have to be performed on the machines. In this paper Batch production job shop Scheduling Problem is solved by using an algorithm considering the shifting bottleneck technique. The main objective was to obtain the best batch size for each job, optimise the makespan and total flow time.

1. Introduction

   Scheduling is the process of assigning the resources over time for the competing activities. It has been the subject of a major amount of literature in the operations research field. The JSSP is recognized as NP-hard [1]. Many techniques have been developed by researchers, to solve the JSSP by optimization and approximation based approaches. The techniques have been limited to small size problems, due to maximum execution time for determining the solutions.

   Mathematical optimization of the JSSP were solved with linear or mixed integer programming for formulating the problem accurately [2,4].

   Besides exhaustive search algorithms based on branch and constraints, several approximation algorithms were developed based on priority rules and active schedule generation [5]. Sophisticated method called shifting bottleneck has been shown to be very successful [30]. The individual batch setup time has to be defined for each machine. The sequence of operations has to be considered for processing the jobs in batch when moving to other machines [7, 8, 13]. A number of heuristic algorithms including genetic algorithm have been used to solve practical big-sized problems in a reasonable computational time. To determine the performances of the algorithms, results were compared with the lower bound of the problem [12]. From the literature reviewed, some of the heuristic algorithms showed very good performances [9, 11].

2. Shifting Bottleneck Technique

   Several heuristic have been developed by several researchers to solve the job shop problem. The Shifting bottleneck algorithm was developed by Adams, Balas, Zawack in 1988. It was modified by Dauzere Teres and Lesserre in 1993. It was developed to solve the general sequence problem where the makespan was minimized [21]. The SB algorithm sequences machines sequentially one at a time. The machines that have not been sequenced and ignored and machines that have been sequenced have their sequences held fixed. At each step the SB algorithm determines the bottleneck machine from the set of machines that have not been sequenced. Every time bottleneck machine is sequenced, re-optimize procedure from set of machines that have been sequenced is performed. The re- optimization is performed by freeing up and re- sequencing each machine in turn with the sequences on the other machines held fixed. Large problems up to 500 operations and 10 machines have been solved. The SB algorithm determines the bottleneck machine with stable and accurate when their many more jobs. The Shifting bottleneck heuristic is an efficient method to find Cmax and Lmax objectives in a job shop. It is an iterative method. At each iteration of the method, a bottleneck machines is identified using 1 | rj | Lmax methodology. A processing sequence of jobs on the machine is found so as to minimize Lmax.

3. Algorithm for batch production JSSP

   For scheduling jobs in batch production it is a tedious job. Each job is constrained with sequence of operations. For the considered real time problem some of the jobs have to be produced in batches. In order to complete the processing of the jobs with minimum makespan an optimized batch size for the production has to be determined.

   An algorithm has been generated to determine the optimized batch size of the jobs. The flow chart is shown in figure 1.

   Figure1: Flow chart to determine batch size of the jobs

   The main objective of simulation is to reduce the idle time of the machine and obtain maximum utilisation from the machines. The setup time, processing time at each machine, number of components to process and the constraints have been considered from the experimental data for the component.

4. Results and Discussion

   For the components the Gantt chart is drawn to analyse the total processing and machine utilisation shown in figure 2. For the present job shop problem a hybrid algorithm is written by decreasing the batch production size so that the shorter jobs will not wait until the whole batch is completed. Based on the sequence of operations the jobs are allotted according to the necessity and completion of the job. The shifting bottleneck method has been used for the proposed batch size problem. The scheduling has been done using different methods to obtain the optimal solution. In order to optimise the total processing time of the JSSP, the proposed algorithm is considered. The machines were constrained and the batch of components to be produced was specified from the algorithm.

   Figure 2: Gantt chart for proposed batch size.

   Figure 3: Comparison of makespan using different techniques

   Figure 4: Comparison of average flow time using different techniques

   The minimum makespan of the JSSP using proposed algorithm was 1074 hrs for the determined batch size and the minimum makespan for the actual problem was 1407 hrs. The average flow time for the JSSP from the proposed algorithm was 699 hrs. It is observed that the average flow time has been decreased by 436 hrs as shown in figure4.

5. Conclusions

   The JSSP has been optimised by using proposed algorithm for the batch size production JSSP. The results obtained from the algorithm decreased the makespan by 23.7% and average flow time by 38.4% when compared with actual batch size problem. The

   proposed algorithm reduced the idle time of the machines and increased the utilization of the machines. The proposed algorithm can be utilised for Job shop scheduling problems with n jobs and m machines where batch production is required for maximum utilisation and allocations of the jobs can be optimised.

6. References

1. Garey. E. L, Johnson. D. S and Sethi. R, "The complexity of flow shop and job shop scheduling", Mathematics of Operations Research, 1976, Vol. 1, pp. 117-129.

2. Brucker. P, Jurisch. B and Sievers. B, "A branch and bound algorithm for job shop scheduling problem", Discrete Applied Math,1994, Vol. 49, pp. 105-127.

3. Artigues. C, Feillet. D, "A branch and bound method for the job shop problem with sequence dependent setup times", Annals of Operations Research, 2008, Vol. 159, No. 1, pp. 135-159.

4. Lorigeon. T, "A dynamic programming algorithm for scheduling jobs in a two-machine open shop with an availability constraint", Journal of the Operational Research Society, 2002, Vol. 53, No. 11, pp. 1239-1246.

5. Ming Liu and Chengbin Chu, Optimal Semi-Online Algorithms for M-Batch-Machine Flow Shop Scheduling, Discrete Math. Algorithm. Appl. 04, 1250051, 2012, pp. 1-7.

6. Kanate Ploydanai, Anan Mungwattana, Algorithm for Solving Job Shop Scheduling Problem Based on machine availability constraint, International Journal on Comuter Science and Engineering, vol.2, No. 05, 2010, pp 1919-1925.

7. Aphirak Khadwilard, Sirikarn Chansombat, Thatchai Thepphakorn, Application of Firely Algorithm and Its Parameter Setting for job Shop Scheduling, The Journal of Industrial Technology, Vol.8 , No. 1 January April 2012, pp 11-10.

8. Shiegheun Koh, Youngjin Kim ; Woonseek Lee, Scheduling two-machine flow shop with a batch processing machine, Computers & Industrial Engineering, 2009. CIE 2009. International Conference, 6-9 July 2009, pp. 46 51.

9. Hua Xuana, Lixin Tangb, Scheduling a hybrid flowshop with batch production at the last stage, Computers & Operations Research, vol. 34, 2007, pp.2718 2733.

10. R. Ramezanian, M.B. Aryanezhad & M.Heydari, A Mathematica Programming Model for Flow Shop Scheduling Problems for Considering Just in Time Production, International Journal of Industrial Engineering & Production Research (September 2010, Volume 21, No. 2, pp 97-104.

11. Jean Paul Watson and J. Christopher Beck, A Hybrid Constraint Programming / Local Search Approach to the Job

    Shop Scheduling Problem, L. Perron and M. Trick (Eds.): CPAIOR 2008, LNCS 5015, pp. 263-277.

12. Wang. T. Y, Wu. K. B, "A revised simulated annealing algorithm for obtaining the minimum total tardiness in job shop scheduling problems", International Journal of Systems Science, 2000, vol. 31, no. 4, pp. 537-542.

13. Larysa Burtseva, Rainier Romero, Salvador Ramirez, Victor Yaurima, Félix F. González-Navarro1 and Pedro Flores Perez, Lot Processing in Hybrid Flow Shop Scheduling Problem, Production Scheduling Edited by Prof. Rodrigo Righi, 11th January 2012, pp 65-96.

14. Liu. B, Wang. L and Jin. Y. H, "An effective hybrid PSO-based algorithm for flow shop scheduling with limited buffers", Computers and Operations Research, 2008 Vol. 35, No. 9, pp. 2791-2806.

15. Ezedeen Kodeekha, Case Studies for Improving FMS Scheduling by Lot Streaming in Flow-Shop Systems, Acta Polytechnica Hungarica, Vol. 5, No. 4, 2008, pp. 125-143.

16. Holland. J. H, Adaptation in Natural and Artificial Systems. Ann Arbor, MI: University of Michigan Press, 1975.

17. Dorndorf. U, and Pesch. E. Evolution based learning in a job-shop scheduling environment. Computers and Operations Research, 1995, Vol. 22, No. 1, pp. 2540.

18. Aydin. M. E. and Fogarty. T. C. A simulated annealing algorithm for multi-agent systems: A job-shop scheduling application. Journal of Intelligent Manufacturing, 2004, Vol. 15, No. 6, pp. 805814.

19. Zhou, R, Nee, A. Y. C. , and Lee, H. P. Performance of an ant colony optimisation algorithm in dynamic job shop scheduling problems. International Journal of Production Research, 2009, Vol. 47, pp. 29032920.

20. Jain, A. S, and Meeran, S. A multi-level hybrid framework applied to the general flow-shop scheduling problem. Computers and Operations Research, 2002, Vol. 29, pp. 18731901.

21. J. Adams, E. Balas, and D. Zawack. The Shifting Bottleneck Procedure For Job Shop Scheduling. Mgmt. Sci., 34(3):391-401, 1988.

22. Wang. L and Zheng, D. Z., An effective hybrid optimisation strategy for job shop scheduling problems. Computers and Operations Research, 2001, Vol. 28, pp. 585 596.

23. Glover. F, "Future paths for integer programming and links to artificial intelligence", Computer and Operation Research, 1986, Vol. 13, No. 5, pp. 533-549.

24. Y. M. Dessouky, C. A. Roberts, G. Wilson, Scheduling multi purpose batch plants with junction constraints, INT. J. PROD. RES., 1996, vol. 34, No. 2, pp. 525 541.

25. Satake, T, Morikawa, K., Takahashi, K. , and Nakamura, N. Simulated annealing approach for minimizing the make-span of the general job shop. International Journal of Production Economics, 1999, Vol. 60, No. 61, pp. 515 522.