The algorithm of Karge Thompson is a heuristic algorithm that allows to obtain, given a specific group of jobs to be produced, the best sequence in terms of time
setup.
Hypothesis:
N indipendent jobs;
delivery dates not relevant;
preemption is not allowed;
set-up time dependent on the sequence of jobs.
Insert matrix with at least 2 jobs with their set-up.
Following steps are:
1 randomly select two jobs from the matrix;
2 select a new job and try to place it in each of the positions of the sequence
current;
3 calculate the corresponding setup time;
4 location the job position that guarentees the lowest set-up time;
5 if there are still jobs return to step 2, otherwise stop.
The algorithm returns the main function with the combination of high and his total time set-up.
To implement algorithm insert your time setup matrix:
A=[setup(job1,job1) setup(job1,job2)...setup(job1,jobN);setup(job2,job1) setup(job2,job2)...setup(job2,jobN);...;setup(jobN,job1)...setup(jobN,jobN)]
and after insert
KargThompson(A)
|
