Evaluating Heuristic Solutionsfor NP-Hard Single Machine Scheduling Problems

Abstract

Scheduling, though being a classical problem of computer science, is still anevolving area of research. Unfortunately, many scheduling problems havinghigh practical significance belong to the classNP-hard, or in simple words, theyare not solved exactly by any efficient algorithm on any computer. In thisdissertation, scheduling problems for the case of single machine problem isstudied. The schemes of evaluating near-to-exact solutions for NP-hardproblems are examined, and an algorithm based on tabu search is devised for the single machine scheduling problem 1 | rj |Cj , where jobs arrive over time,preemption is not allowed, and the objective is to minimize the total completiontime.