Minimization of maximum lateness under linear deterioration |
| |
Authors: | Y S Hsu B M T Lin |
| |
Institution: | a Department of Computer Science and Information Engineering, Ming Chuan University, Tao-Yuan 333, Taiwan;b Department of Information Management, National Chi Nan University, Pu-Li, Nan-Tou 545, Taiwan |
| |
Abstract: | This paper considers a single-machine scheduling problem to minimize the maximum lateness. The processing time of each job is a linear function of the time when the job starts processing. This problem is known to be
-hard in the literature. In this paper, we design a branch-and-bound algorithm for deriving exact solutions by incorporating several properties concerning dominance relations and lower bounds. These properties produce synergic effects in accelerating the solution finding process such that the algorithm can solve problems of 100 jobs within 1 min on average. To compose approximate solutions, we revise a heuristic algorithm available in the literature and propose several hybrid variants. Numerical results evince that the proposed approaches are very effective in successfully reporting optimal solutions for most of the test cases. |
| |
Keywords: | Operations scheduling Linear deterioration Maximum lateness Branch-and-bound algorithm Heuristic algorithm |
本文献已被 ScienceDirect 等数据库收录! |
|