|
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.
|