|
Scheduling plays an important role in shop production
planning. A schedule
determines not only the process sequences of jobs on the
resources, but also the start and finish times as well. Such
resources may include the work force, facilities or
machines, which are limited usually. Therefore, how to increase
the utilization of the limited resources becomes a challenge
to who does the scheduling jobs. A good schedule not
only increases the utilization of the resources, but also makes
the jobs to meet the due dates as far as possible.
The job shop scheduling problem to minimize the total tardiness
is a complex and large scale combinatorial optimization
problem. Owing to the problem''s complexity and
intractability, it has not been adequately solved. The Simulated
Annealing (SA) is a good algorithm for solving difficult
optimization problems. This algorithm is particularly
appropriate for solving large scale problems that are difficult
to formulate and no satisfactory tailored algorithms are
available. Thus, this research employs the simulated annealing
algorithm to solve the job shop scheduling problems. To improve
the solution quality (measured in total tardiness) and
efficiency, also presented herein are two neighboring
solution generation mechanisms, a total tardiness calculation, a
parameter set design, and an initial solution search
procedure. The proposed parameter set design procedure also
takes the restriction of computational time into account.
The computational results show that the solution quality of the
SA outperforms the more tailored algorithm MEHA.
About the two generation mechanisms of the SA, SA1
performs better than SA2. Although the performance measure is
total tardiness, the number of tardy jobs and the conditional
mean tardiness from SA also performs better than other
algorithms. The results also show that the parameter set gets
from the design procedure is appropriate.
|