Approximation methods for total completion time with set-up times

Abstract

This research considers the problem of scheduling jobs on a single machine to minimize the objective function , the sum of completion time .The jobs partitioned into families , and a set-up time is necessary for scheduling the first job and when there is a switch in processing jobs from one family to jobs of another family . To solve this problem some known approximation methods are modified , namely the tree type heuristic (TTH) and tow local search methods descend method (DM) and simulated annealing method (SAM) . The performance of approximation methods can be tested on a large class of test problems. Keywords: Scheduling , single machine , set-up time ,heuristics