Teknik Relaksasi Lagrange untuk Penjadwalan Pekerjaan Majemuk dengan Penggunaan Sumberdaya Simultan

Suprayogi Suprayogi, Valentine Valentine


This paper discusses the multiple jobs scheduling problem with simultaneous resources. The problem involves one or more jobs with each job consist of a set of operations. Each operation is performed by more than one resource simultaneously. Number of units of each resource used for performing an operation is one or more units. The problem deals with determining a schedule of operations minimizing total weighted tardiness. In this paper, solution techniques based on Lagrangian relaxation are proposed. In general, the Lagrangian relaxation technique consists of three parts run iteratively, i.e., (1) solving individual job problems, (2) obtaining a feasible solution, and (3) solving a Lagrangian dual problem. For solving the individual job problems, two approaches are applied, i.e., enumeration and dynamic program¬ming. In this paper, the Lagrangian relaxation technique using the enumeration and dynamic programming approaches are called RL1 and RL2, respectively. The solution techniques proposed are examined using a set of hypothetical instances. Numerical experiments are carried out to compare the performance of RL1, RL2, and two others solution techniques (optimal and genetic algorithm techniques). Numerical experiments show that RL2 is more efficient than RL1. In terms of the solution quality, it is shown that RL2 gives same results compared to the optimal technique and genetic algorithm. However, both RL2 and genetic algorithm can handle larger problems efficiently.


  1. Dobson, G., and Karmarkar, U.S., Simultaneous Resource Scheduling to Minimize Weighted Flow Times, Operations Research, 37, 1989, pp. 592-600.
  2. Dobson, G., and Khosla, I., Simultaneous Resource Scheduling with Batching to Minimize Weighted Flow Times, IEE Transactions, 27, 1995, pp. 587-598.
  3. Suprayogi dan Mardiono, N.M.T, Pengembangan Algoritma bagi Masalah Penjadwalan Banyak Job Operasi Tunggal Banyak Sumber Paralel Simultan, Jurnal Teknik dan Manajemen Industri, 17, 1997, pp. 39-49.
  4. Luh. P.B., Liu, F., and Moser, B., Scheduling of Design Projects with Uncertain Number of Iterations, European Journal of Operational Research, 113, 1999, pp. 575-592.
  5. Toha, I.S., dan Halim, A.H., Algoritma penjadwalan produksi berbasis jaringan untuk sumberdaya tunggal dan simultan, Jurnal Teknik dan Manajemen Industri, 19 (2), 1999, pp. 10-20.
  6. Suprayogi dan Toha, I.S., Model Pemrograman Linier Bilangan Bulat untuk Masalah Penjadwalan Sumber-Majemuk Paralel Simultan, Jurnal Teknik dan Manajemen Industri, 22 (1), 2002, pp. 27-38.
  7. Suprayogi dan Partono, S., Pendekatan Pemecahan Berbasis Relaksasi Lagrange untuk Masalah Penjadwalan Job-Majemuk, Operasi-Majemuk Sumber-Majemuk Paralel Simultan, Prosiding Seminar Sistem Produksi VII 2005, Surabaya, 2005, pp. 907-920
  8. Suprayogi and Partono, S., Lagrangian Relaxation Technique for Solving Simultaneous Multiresource Scheduling Problems, Proceedings of Asia Pacific Conference on Manufacturing Systems (APCOMS) 2007, Bali, 2007.
  9. Suprayogi, Siregar, A., and Aji, T., Solving Multiproject Constrained Scheduling Problems with Simultaneous Multiresource using Genetic Algorithm, Proceedings of Asia Pacific Conference on Manufacturing Systems (APCOMS) 2007, Bali, 2007.
  10. Wu, J.-Z., and Chien, C.-F., Modeling semi-conductor testing job scheduling and dynamic testing machine configuration, Expert Systems with Applications, 35, 2008, pp. 485–496.
  11. Wu, J.-Z, Hao, X,-C., Chien, C.-F., Gen, M., A Novel Bi-Vector Encoding Genetic Algorithm for the Simultaneous Multiple Resources Scheduling Problem, Journal of Intelligent Manufacturing, 23, 2012, pp. 2255-2270.
  12. Kaskavelis, C.A., and Caramanis. M.C., A Lagrangian Relaxation Based Algorithm for Scheduling Multiple-Part Production-System: Industrial Implementation Experience, Proceedings of the 1994 Japan-U.S.A. Symposium on Flexible Automation, Kobe, Japan, July 11-18, 1994, pp.173-180.
  13. Kaskavelis, C.A., and Caramanis. M.C., Application of a Lagrangian Relaxation Scheduling Based Algorithm to A Semiconductor Testing Facility, Proceedings of the Fourth International Conference on Computer Integrated Manufacturing and Automation Technology, Troy, NY, October 10-12., 1994, pp. 106-112.
  14. Kaskavelis. C.A., and Caramanis, M.C., Efficient Lagrangian Relaxation Algorithms for Industry Size Job-shop Scheduling Problems, IEE Transactions, 30, 1998, pp. 1085-1097.
  15. Luh, P.B., Hoitomt, D.J., Max, E., and Pattipati, K.R., Schedule Generation and Reconfiguration for Parallel Machines, IEEE Transactions on Robotics and Automation, 6 (6), 1990, pp. 687-696.
  16. Hoitomt, D.J., Luh, P.B., and Pattipati, K.R., A Practical Approach to Job Shop Scheduling Problems, IEEE Transactions on Robotics dan Automation, 9 (1), 1993, pp. 1-13.
  17. Luh, P.B., and Hoitomt, D.J., Scheduling of Manufacturing Systems using the Lagrangian Relaxation Technique, IEEE Transaction on Automatic Control, 38 (7), 1993, pp. 1066-1079.
  18. Luh, P.B., Wang, J.H., Wang, J.L., Tomastik, R.N., and Howes, T.D., Near Optimal Scheduling of Manufacturing Systems with Presence of Batch Machines and Setup Requirements. CIRP Annals – Manufacturing Technology, 46 (1), 1997, pp, 397–402.
  19. Chen, T.R. and Hsia, T.C., Scheduling for IC Sort and Test Facilities with Precedence Constraints via Lagrangian Relaxation , Journal of Manufacturing Systems, 16 (2), 1997, 117-128.
  20. Luh, P.B., Zhou, X., and Tomastik, R.N., An Effective Method to Reduce Inventory in Job Shops, IEEE Transactions on Robotics and Automation, 16 (4), 2000, pp. 420-424.
  21. Zhang, Y., Luh, P.B., Yoneda, K., Kano, T., and Kyoya, Y., Mixed-Model Assembly Line Scheduling using the Lagrangian Relaxation Tech-nique, Proceedings of the 1997 IEEE International Conference on Control Applications, Hartford, CT, U.S.A., October 5-7, 1997, pp. 429-434.
  22. Zhang, Y., Luh, P.B., Narimatsu, K., Moriya, T., Shimada, T., and Fang, L., A Macro-Level Scheduling Method Using Lagrangian Relaxation, IEEE Transactions on Robotics and Automation, 17 (1), 2001, pp. 70-79.
  23. Morton, T.E., and Pentico, D.W., Heuristic Scheduling System: with Applications to Production Systems and Project Management, John Wiley and Sons, New York, U.S.A., 1993.
  24. Pritsker, A.A.B., Watters, L.J., and Wolfe, P.M., Multiproject Scheduling with Limited Resources: A Zero-One Programming Approach, Management Science 16, 1969, pp. 93-108.
  25. Fisher, M.L., An Application Oriented Guide to Lagrangian Relaxation, Interfaces 15, 1985, pp. 10-21.

Full Text: PDF

Instructions for Preparing Papers for JTI.docx
Panduan untuk Menulis di JTI.docx

The Journal is published by The Institute of Research & Community Outreach - Petra Christian University. It available online supported by Directorate General of Higher Education - Ministry of National Education - Republic of Indonesia.

©All right reserved 2016.Jurnal Teknik Industri, ISSN: 1411-2485, e-ISSN: 2087-7439

shopify traffic stats
View My Stats

Copyright © Research Center Web-Dev Team