Heuristic algorithms to minimize total tardiness in an identical-parallel-machine scheduling problem with flexible maintenance  

Oleh:

Lee, Ju-Yong ; Kim, Yeong-Dae ; Jeong, BongJoo

Jenis: Article from Proceeding
Dalam koleksi: The 14th Asia Pacific Industrial Engineering and Management Systems Conference (APIEMS), 3-6 December 2013 Cebu, Philippines, page 1-9.
Topik: scheduling; identical parallel machines; flexible maintenance; total tardiness; heuristic
Fulltext: 1241.pdf (524.27KB)

Isi artikel

In this study, we consider a problem of scheduling jobs on identical parallel machines that are not continuously available with the objective of minimizing total tardiness of jobs. Each machine requires (preventive) maintenance tasks which have to be started within a given cumulative working time limit after the previous maintenance. The starting time of a maintenance task is not fixed but flexible, that is, a maintenance activity can be started at any time unless the cumulative working time after the end of the previous maintenance exceeds the given limit. This problem can be easily proven to be NP-hard. We develop two-phase heuristic algorithms. In the algorithm, an initial solution is obtained with a lower bound-based algorithm or an algorithm modified from an existing algorithm called KPM in the first phase, and then, it is improved with local search methods in the second phase. For evaluation of the performance of the proposed algorithms, computational experiments are performed on randomly generated test instances and results are reported.

Opini Anda

Klik untuk menuliskan opini Anda tentang koleksi ini!

Kembali