Application of Johnson’s algorithm in processing jobs through two-machine system

• Autorzy: Okwu Modestus , Emovon Ikuobase

Identyfikatory

DOI

10.30464/jmee.2020.4.1.33

• Języki publikacji: EN

Abstrakty

EN

The purpose of this research is to effectively schedule jobs in a production company using heuristic Johnson’s algorithm. A popular pure water production factory, Iterlene industrial services limited (IISL) located at Effurun, Nigeria was investigated and it was noticed that different sizes of jobs (bottled water) are produced ranging from 25 cl, 50 cl, 60 cl, 75 cl, and 150 cl respectively, which are processed through the filling machine (FM1) and capping machine (CM2). In the order FM1CM2. Each job has to pass through the same sequence of operations. Jobs are assigned in such a way that a job is assigned on FM1 first and once processing is completed on FM1, it is assigned to CM2 and passing is not allowed. The idle time for the production of 500 bottles of water was estimated to be 1020 seconds (17.00 mins.). Johnson’s algorithm was applied to minimize the idle time for both FM1 and CM2 by determining the optimal sequence of the processed jobs. This was achieved within 780 seconds (13.00 mins.). Conclusively, the minimization of total elapsed time between the completion of first and last job was achieved. This would greatly improve productivity, effectiveness, and profitability at iterlene factory.

Słowa kluczowe

EN

Johnson algorithm; heuristic technique; sequencing; scheduling

PL

algorytm Johnsona; heurystyka; sekwencjonowanie; planowanie

• Wydawca: Wydawnictwo Uczelniane Politechniki Koszalińskiej
• Czasopismo: Journal of Mechanical and Energy Engineering
• Rocznik: 2020
• Tom: Vol. 4, No 1
• Strony: 33--38
• Opis fizyczny: Bibliogr. 20 poz., rys., tab., wykr.

Twórcy

autor

Okwu Modestus

• Federal University of Petroleum Resources Effurun, Warri, College of Technology, Department of Mechanical Engineering, Delta State, Nigeria

autor

Emovon Ikuobase

• Federal University of Petroleum Resources Effurun, Warri, College of Technology, Department of Mechanical Engineering, Delta State, Nigeria

Bibliografia

• 1. Bellanger A., Hanafi S., and Wilbaut C. (2013). “Three-stage hybrid flow shop model for cross-docking,” Computers & Operations Research, vol. 40, no. 4, pp. 1109-1121
• 2. Brucker P. (1998). Textbook on Scheduling Algorithms, Springer-Verlag Berlin, Heidelberg
• 3. Black, Paul E. (2004), "Johnson's Algorithm", Dictionary of Algorithms and Data Structures, National Institute of Standards and Technology.
• 4. Cheng T.C.E., Wu C.C., J. C. Chen, W. H. Wu, and S. R. Cheng (2013). “Two-machine flowshop scheduling witha truncated learning function to minimize the makespan” Int. J. Production Economics, no. 141, pp. 79-86, 2013.
• 5. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), “Introduction to Algorithms”, MIT Press and McGraw-Hill, ISBN 978-0-262-03293-3
• 6. Dong J., Hu J., and Chen Y. (2013) “Minimizing makespan in a two stage hybrid flow shop scheduling problem with open shop in one stage,” J. Chinese Univ., vol. 28, no. 3, pp. 358-368
• 7. Glaser A. and Sinha M. (2010) Scheduling Programming Activities and Johnson's Algorithm. Journal of Management, administration and support. 5 (1-7)
• 8. Hekmatfar M., Ghomi S.M.T.F., and Karimi B. (2011).“Two stage reentrant hybrid flow shop with setup times and the criterion of minimizing makespan,” Applied Soft Computing, vol.11, no. 8, pp. 4530-4539
• 9. Hu M. and Veeravalli B. (2013) “Requirement-aware scheduling of bagof-tasks applications on grids with dynamic resilience,” IEEE Trans. Comput., vol. 62, no 10, pp. 2108-2114
• 10. Johnson, D. B. (1977). Efficient algorithms for shortest paths in sparse networks. Journal of the Association for Computing Machinery, volume 24, pp. 1-13
• 11. Liao C.J., Lee C.H. and Lee H.C. (2015) “An efficient heuristic for a two-stage assembly scheduling problem with batch setup times to minimize makespan,” Comput. & Indust. Engineering, no. 88, pp. 317-325
• 12. Mansouria S.A., Aktasb E. and Besikcic U. “Green scheduling of a two-machine flowshop: Trade-off between makespan and energy consumption,” Eur. J. of Operational Research, no. 248, pp. 772-788
• 13. Nikzad F., Rezaeian J., Mahdavi I., and Rastgar I. (2015) “Scheduling of multi-component products in a two-stage flexible flow shop,” Applied Soft Computing, no. 32, pp. 132-143
• 14. Pogorilyy S.D., Slynko M.S., Rustamov Y.I. (2017) Research and Development of Johnson's Algorithm Parallel Schemes in GPGPU Technology, TWMS, Journal of Pure and Applied Mathematics, 8, (1),12-21
• 15. Russell, S. J.; Norvig, P. (2003). “Artificial Intelligence: A Modern Approach”. Upper Saddle River, N.J.: Prentice Hall. pp. 97-104. ISBN 0-13-790395-2
• 16. Sándor R., Tibor Tóth, János Göndri-Nagy (2003). A multiple (extended) application of the Johnson Algorithm for the Two-Machine Manufacturing Cell Scheduling Based on Group Technology. Journal of Production Systems and Information Engineering. 1 (55-69)
• 17. Sanan S., Leena jain, Bharti Kappor (2013). Shortest Path Algorithm, International Journal of Application or Innovation in Engineering & Management (IJAIEM), Volume 2, Issue 7, 316-320
• 18. Sharma J.K. (2013). Operations Research Theory and Applications. A book published by Amitabh Nagpal for Macmillan Publishers India Ltd 3A, DLF corporate Park, Gurgaon 122 002 (Haryana), India. 5th edition. ISBN: 978-9350-59336-3
• 19. Xiong Y., Suzhen Huang, Min Wu, Jinhua She, Keyuan Jiang (2014) A Johnson's-Rule-Based Genetic Algorithm for Two-Stage-Task Scheduling Problem in Data-Centers of Cloud Computing. Journal of Latex Class Files 13(9) 1-14
• 20. Zotkiewicz, M. Guzek, D. Kliazovich and P. Bouvry (2016) “Minimum Dependencies Energy-Efficient Scheduling in Data Centers,” IEEE Trans. Parallel Distrib. Syst., vol. 27, no. 12, pp. 3561-3574

Uwagi

PL

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).