Teknik Relaksasi Lagrange untuk Penjadwalan Pekerjaan Majemuk dengan Penggunaan Sumberdaya Simultan
Abstract: 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.
Penulis: Suprayogi, Valentine
Kode Jurnal: jptindustridd150199
