Scheduling jobs divided into classes

Question

There are 'n' different types of jobs, e.g. small letters, capital letters and numbers. Switching from one type of job to another is more time consuming (S) than switching to job from the same group (C) . Every job has its deadline and process time.

For example :

n = 3; (small letters, capital letters and numbers)
S = 5;
C = 1;

Job/Deadline/Process Time

a/5/2 1/15/3 b/20/4 R/25/1

a,1,b,R : 2+(5)+3+(5)+4+(5)+1 = 25 a,b,1,R : 2+(1)+4+(5)+4+(5)+1 = 21

Is there any algorithm which solves that problem besides metaheuristic ?

Answer 1

Looks like this is Job-shop problem that is a generalization of the traveling salesman problem so it is NP-hard and doesn't have optimal algorithm. Try Job shop scheduling article as starting point of your research