Simulation Of Job Shop Scheduling Problem

Simulation Of Job Shop Scheduling Problem

Katuru Phani Raja Kumar1, Dr. V Kamala 2, Dr. ACS Kumar3

1*Project Manager, IBG Manufacturing, Mahindra Satyam USA/India

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

3Professor, Mechanical Engineering JNTUH (Rtd) Hyderabad

Abstract

In a manufacturing system Job Shop Scheduling is an important aspect where the maximum utilization of the resources should be considered. The computer simulation of distinct events is mostly used for manufacturing design, but it is given a slight consideration in production scheduling. The Job Shop Scheduling Problem is solved by using Flexsim simulation software with an objective to optimise the total flow time.

1. Introduction

   Scheduling is the process of allocating shared resources over time for competing activities is known as scheduling. It has been the subject of a significant amount of literature in the operations research field. The JSSP is categorised into NP-hard, but it is one of the worst members in the class. An indication of this is given by the fact that one 10×10 problem formulated remained unsolved for over 20 years.Many techniques have been developed by researchers, to solve the JSSP by optimization and approximation based approaches. Due to maximum consumption of time for determining the solutions, they are limited to small size problems only.

   Mathematical optimization of the JSSP were solved with linear or mixed integer programming for formulating the problem accurately.

   Besides exhaustive search algorithms based on branch and constraints, several approximation algorithms were developed based on priority rules and active schedule generation [21]. Sophisticated method called shifting bottleneck has been shown to be very successful [30]. Additionally, stochastic approaches such as simulated annealing, Tabu search [15, 26, 32] and genetic algorithms have been recently applied with good success [11,19].

2. Shortest Processing Time Technique

   The shortest job are handled first and completed. The shortest processing time (SPT) implies that the next job to be processed is the one that has the least time necessary to complete. The philosophy here is to get the smallest jobs over quickly, which gives a physiological impression that one is being more productive. The problem with this approach is that large jobs, which might be more urgent, are done later. Jobs are sequenced in non decreasing order of processing times.

3. Simulation of JSSP

   For analyzing and solving problems that exist in real systems simulation is used as an applied technology. It provides the context for the book by defining what simulation is and the characteristics of the systems in which simulation is applied. The processing systems are used in all areas of manufacturing and mining, as well as service operations transportation, and distribution. Simulation is used to add values to all facets of decision making.

   Often the scope of a manufacturing simulation includes one or more production lines. The productions lines are controlled by a schedule to indicate the type of products to be produced, which equipment has to be used, and the order in which production should take place. Simulating this environment requires a large amount of custom coding for all the operating variables. In Flexsim, the production scheduling objects eliminate the need for that custom code, simplifying the process dramatically. For simulation purposes, the production environment is defined as follows: Line: A group of equipment that produces a single output at a time System: One or more lines that are scheduled as a group.

   The job shop scheduling problem is simulated using SPT technique. The main objective of simulation is to reduce the idle time of the machine and obtain maximum utilisation from the machines. Flexsim

   software was used to optimise the scheduling of the component. 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 component the Gantt chart is drawn to analyse the total processing and machine utilisation shown in figure 1. By using the shortest processing time technique the average flow time is in 538.4 hrs. The total utilisation is determined to be 92.91% by using SPT. The total delays from the accumulations of flow time is 78.45hrs

   48.00

   The state analysis for processing, releasing, setup time, idle time was obtained after simulating the process lay out.

   RM

   SGS

   RT

   3DBHT

   M

   VHT

   CG

   11.30

   48.00

   16.20

   23.30

   96.00

   4.30 14.00

   7.00

   5.00 3.00

   Figure 3: utilisation of machines for the above model

   3DAHT

   2DAHT

   CNCEDM

   P

   18.50

   14.30

   55.30

   11.00

   14.30

   MFEDM

   GATEEDM

   T

   Figure 1: Gantt chart using SPT.

   37.30

   16.30

   3.00 1.00

   2.00

   Figure 4: bar chart representing the utilisation of machines

   In order to optimise the total processing time of the JSSP, computer simulation is considered. Using Flexsim software the flow of the raw material from the initial stage to the final product output was designed according the job shop arrangement of the processed component. The machines were constrained and the batch of components to be produced was specified at the source. All the jobs were collected at the sink.

   Figure 2: model layout of the JSSP in Flexsim

   Figure 5: Simulation result for processing using Flexsim.

   Figure 6: Comparision of Total Flow time for JSSP

   The total flow time for the JSSP from the computer simulation was 338.30 hrs. It is observed that the flow time has been decreased by 200.10hrs as shown in figure6.

5. Conclusions

   The JSSP has been simulated using Flexsim software. The simulation results optimised the total processing time by 35% of the total processing time determined by the SPT technique. The simulation model reduced the idle time of the machines and increased the utilization of the machines. The computer simulation can be utilised to for Job shop scheduling problems with n jobs and m machines so that 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. Potts. C. N and Van Wassonhove. L. N, "Dynamic programming and decomposition approaches for the single machine total tardiness problem", European Journal of Operational Research, 1987, Vol. 32, pp, 405-414.

6. Kanate Ploydanai, Anan Mungwattana, Algorithm for Solving Job Shop Scheduling Problem Based on machine availability constraint, International Jurnal on Computer 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. Sultana Parveen and Hafiz Ullah, Review On Job and Flow Shop Scheduling using multi criteria decision making, Journal of Mechanical engineering, Vol. ME 41, No. 2, December 2010, Transaction of the Mech. Eng. Div., The Institution of Engineers, Bangladesh, pp 130-146.

9. Ivan Lazar, Review On Solving the Job Shop Scheduling Problem: Recent Development and Trends (2012, Transfer Inovacii, 23/2012, pp 55-60.

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. Ching Fang Liaw, Theory of Methodology A hybrid genetic algorithm for the open shop scheduling problem, European Journal of Operational Research, 124 (2000), pp 28 42.

12. 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.

13. Zhang. C. Y, Li. P. G, Rao. Y. Q, "A very fast TS/SA algorithm for the job shop scheduling problem", Computers and Operations Research, 2008, Vol. 35, pp. 282-294.

14. Nowicki. E andSmutnicki. C, "A fast taboo search algorithm for the job shop scheduling problem", Management Science, 1996 Vol. 41, No. 6, pp. 113-125.

15. Dell. A. M, Trubian. M, "Applying tabu-search to job shop scheduling problem," Annals of Operations Research, 1993, Vol. 41, No. 3, pp. 231-252.

16. 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.

17. Kolonko. M, "Some new results on simulated annealing applied to the job shop scheduling problem", European Journal of Operational Research, 1999, vol. 113, no. 1, pp. 123-136.

18. Moon. I, Lee. S and Bae. H, "Genetic algorithms for job shop scheduling problems with alternative routings", International Journal of Production Research, 2008, Vol. 46, No. 10, pp. 2695-2705.

19. Goncalves. J. F, Mendes. J. J. D. M and, Resende. M. G. C, "A hybrid genetic algorithm for the job shop scheduling problem", European Journal of Operational Research, 2005, Vol. 167, No. 1, pp. 77-95.

20. Bierwirth. C and Mattfeld. D. C, "Production scheduling and rescheduling with genetic algorithms", Evolutionary Computation, 1999, Vol. 7, No. 1, pp. 1-17.

21. 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.

22. Tasgetiren. M. F, Liang. Y. C and Sevkli. M, "A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem", European Journal of Operational Research, 2007, Vol. 177, No. 3, pp. 1930-1947.

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

24. Della Croce. F. Tadei. R. andVolta. G. A genetic algorithm for the job shop problem. Computers and Operations Research, 1995, Vol. 22, No. 1,pp. 1524.

25. 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.

26. Eswarmurthy. V. and Tamilarasi. A. Hybridizing tabu search with ant colony optimization for solving job shop scheduling problem. The International Journal of Advanced Manufacturing Technology, 2009, Vol. 40, pp. 10041015.

27. Park. B. J. , Choi, H. R. , and Kim. H. S. A hybrid genetic algorithm for the job shop scheduling problems. Computers and Industrial Engineering, 2003, Vol. 45, pp. 597613.

28. 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.

29. Gao. J. Gen. M., and Sun. L. Scheduling jobs and maintenances in flexible job shop with a hybrid genetic algorithm. Journal of Intelligent Manufacturing, 2006, Vol. 17, No. 4, pp. 493507.

30. Pezzella. F. and Merelli. E. A tabu search method guided by shifting bottleneck for the job shop scheduling problem. European Journal of Operation Research, 2000, Vol. 120, pp. 297310.

31. Pezzella. F. , Morganti. G. , and Ciaschetti. G. A genetic algorithm for the flexible job-shop scheduling problem. Computers and Operations Research, 2008, Vol. 35, pp. 32023212.

32. Chen. L, Bostel. N, Dejax, P. , Cai. J, and xi. L. A tabu search algorithm for the integrated scheduling problem of container handling systems in a maritime terminal. European Journal of Operational Research, 2007, Vol. 181, No. 1, pp. 4058.

33. 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.

34. 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.

35. 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. 515522.

36. 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.

37. González, M. A. , Vela, C. R. , and Varela, R. Genetic algorithm combined with tabu search for the job shop scheduling problem with setup times' methods and models in artificial and natural computation. A homage to professor Mira's scientific legacy. Lecture Notes in Computer Science, 5601/2009, pp. 265274.

38. Thamilselvan, R, P. Balasubramanie, Integration of Genetic Algorithm with Tabu Search for Job Shop Scheduling with Unordered Subsequence Exchange Crossover. Journal of Computer Science, 8(5): 681-693. DOI: 10. 3844/jcssp. 2012, pp 681-693.

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