Comparative evaluation of heuristic algorithms for the single machine scheduling problem with two operations per job and time-lags |
| |
Authors: | Jatinder N D Gupta |
| |
Institution: | (1) Department of Management, Ball State University, 47306 Muncie, IN, USA |
| |
Abstract: | This paper shows that the single machine scheduling problem with multiple operations per job separated by minimum specified time-lags is NP-hard in the strong sense. Seven simple and polynomially bounded heuristic algorithms are developed for its solution when each job requires only two operations. Empirical evaluation shows that the percentage deviation of the heuristic solutions from their lower bounds is quite low and the effectiveness of these heuristic algorithms in finding optimal schedules increases with an increase in the number of jobs. |
| |
Keywords: | Single machine scheduling multiple operations time-lags NP-hardness heuristics worst-case analysis computational results |
本文献已被 SpringerLink 等数据库收录! |