Proceedings of SKISE Spring Conference, May 16 – 17, 2003

A Modified Simulated Annealing for One-machine Scheduling Problem

Junjae Chae
TexasA&MUniversity
College Station, Texas
USA / DongJu Lee
KongjuNational
University
Yesan, Korea
Abstract
In this paper a modified simulated annealing approach for solving single-machine mean tardiness scheduling problems is proposed. The results of the simulation indicate that the proposed method provides more stable solutions than those of previous studies. The proposed method also provides better quality solutions for large-size problems.
Key-words : simulated annealing, scheduling, mean tardiness

1

Proceedings of SKISE Spring Conference, May 16 – 17, 2003

1. INTRODUCTION

Single machine scheduling problems are important; the results that can be obtained for single machine models not only provide insight into single-machine environments but also provide a basis for heuristics for more complicated machine environments. In practice, scheduling problems in more complicated machine environments are often decomposed into sub-problems that deal with single machine as there are situations where job shops with more than one machine can be treated as a single machine problem. This is the case for example when one machine acts as a bottle-neck [1]. It makes sense to treat the problem as a single machine problem, if only to get an approximation to the problem [2].

The one-machine mean tardiness problem is NP-hard [3]. Optimal solutions to the scheduling problem can be obtained through enumeration methods, such as branch and bound [4] and dynamic programming [5]. However, these methods may involve long computational times to produce optimal solutions even though the size of problem is not big since the number of iterations is increased by factorial time. This leads to the need for the development of a heuristic procedure.

In this paper, a modified simulated annealing algorithm for solving one-machine mean tardiness problems is proposed. The proposed algorithm is compared to Ben-Daya's simulated annealing algorithm [1]. Ben-Daya's approach has been compared to the heuristic of Fry et al. [6] and Holsenback and Russel [7] through a simulation experiment involving a set of randomly generated problems, and the solution obtained there using the simulated annealing algorithm proved superior to those obtained using the other two heuristics. The proposed modified simulated annealing algorithm provides favorable solutions that are superior to the simulated annealing algorithm.

This paper is organized as follows. Heuristic algorithms used for the one machine mean tardiness scheduling problem are briefly described for background in the next section. The one-machine mean tardiness scheduling problem is described in Section 3, and its solution procedure, the modified simulated annealing approach, is presented in Section 4. The computation results are compared in Section 5 and concluding remarks are then presented in the last section.

2. BACKGROUND

As mentioned above, the one-machine mean tardiness problem has been proven to be NP-hard and it causes exponential growth in computation time. Thus, the investigations are focused on developing good heuristics to get a quality solution with a reasonable amount of computational effort.

Fry et al.[6] proposed a heuristic based on the adjacent pairwise interchange (API) methodology for solving the one-machine scheduling problem. They used three different API strategies with three different initial sequences. If the interchange generates a favorable sequence, switching is made and the process continues until there is no further switching that produces a better sequence.

Holsenback and Russel [7] developed a heuristic method using modified due dates derived from Emmons' Theorem Dominance Relationship [9]. The authors identified the jobs that have reducible tardiness; to select from the potential jobs for the last position, they developed an evaluation strategy based on net benefit of relocation (NBR). The tardiness of the jobs following this particular one is reduced after the relocation, whereas the tardiness of the job itself increased. The algorithm selects a job with the largest positive NBR among the candidate jobs and this process starts from the end of the initial EDD sequence and continues until all the jobs of the sequence are considered. For the details of the algorithm, refer to Holsenback and Russell [7].

Potts and Van Wassenhove [8] proposed a simulated annealing algorithm for single machine mean tardiness problems. They generate the neighborhood using all pair of interchanges which makes their neighborhood size n(n-1)/2. Ben-Daya and Al-Fawzan [1] also proposed a simulated annealing algorithm that reduced neighborhood size to 1 and simplifying procedures and operational parameters.

3. PROBLEM DESCRIPTION

The single-machine mean tardiness scheduling problem can be described as follows: at time zero, there exist n jobs to be processed on a single machine. Each job has its processing time (p) and its due date (d). The objective is to find a sequence that minimizes the mean tardiness () defined as follows:
,

where nindicates number of job, and are completion time and due date of ith job respectively.

The following assumptions presented by Conway et al. [10] and accepted most researchers are adopted for the considered problem:

piis an integer and is sequence independent,

diis an integer measured from zero when all jobs are available for processing,

the machine is available continuously to process n jobs, and

there are no setup times or time losses due to machine loading and unloading.

4. SOLUTION METHODOLOGY - MODIFIED SIMULATED ANNEALING

The methodology of MSA is identical to the general simulated annealing algorithm except a greedy algorithm is added to each iteration with some probability. The chance to apply this greedy heuristic to SA is decreasing as the number of iteration is increased. This greedy algorithm finds the local optima by swapping the sequence from the first job to last job (n). Whenever the new sequence improves the mean tardiness, the algorithm switches the sequence of the job. This procedure slows the SA but it gives the procedure a chance to find more favorable solutions in the early stages of the procedure.

SA begins with a randomly generated initial sequence and a new sequence is generated by randomly interchanging two jobs. The new sequence is accepted if its mean tardiness is better than that of the original sequence, otherwise it is accepted with a probability that decreases as the process evolves. The acceptance probability is of the formPa=e, where is a control parameter which is increased during the search andis the increase in mean tardiness. If the tardiness of a new sequence is increased after the random pairwise interchange, the new sequence is accepted if , PaRwhere Ris a random number between 0 and 1. This process is terminated when some stopping criterion is satisfied.

In SA, the control parameter, , is calculated as =COUNTSTEP2, where COUNT is incremented by 1 at every iteration and STEP=2. In MSA, this control parameter is treated as temperature and is reduced by a temperature reduction factor, r. In each temperature, the number of swapping procedures is limited by NOVER and NLIMIT, which are set proportional to the number of jobs. The MSA set those criteria as 100*n and 10*n, respectively. The algorithm stops when it reaches the stopping criteria, ITEMPMAX=100, which indicates the number of temperature reductions. The procedure also stops if there is no swapping occurring after 100*n trials.

Fig. 1 Flow chart for the MSA algorithm

After the random job interchange, the greedy algorithm is applied to a given sequence with probability of p for accelerating the annealing procedure if the interchange improves the mean tardiness. The probability, p, is of the form

where, c is constant, ITEMP is the number of temperature reductions. This procedure makes the MSA take longer than SA; the probability of acceptance with the greedy algorithm in the main search procedure is counter proportional to the number of jobs and the number of temperature reductions. This restriction is for preventing the search procedure from being trapped in local optima in solid state - low temperature in annealing procedure - of the algorithm. Fig. 1 shows the algorithm of MSA.

5. COMPARATIVE STUDY

The modified simulated annealing algorithm described in Section 4, and the Ben-daya's Simulated Annealing were coded in C/C++ and run a Pentium 4 class computer (3.06 GHz of CPU, 512 MB of RAM, and Window XP Professional operating interface).

A set of randomly generated problems was used. Smaller size problems (n = 20,40,60,80) were generated using processing time in the range of [0, 100]. The processing time for the larger size problem set (n = 100,150) was in the range of [0, 200]. Due dates with certain levels of tightness were generated as proposed in [8]. In this paper, 0.8 of the RDD (range of due dates) and 0.6 of the TF (average tardiness factor) were adopted when the due date for each job is generated from the uniform distribution in the following range:

The results of the smaller problem set shown in Table 1 indicate that there is not much difference between the solution quality generated by these two algorithms (n = 20,40). It seems, however, the MSA generates more favorable solutions as the problem size increases.

The solution time for SA is much faster than that of the MSA; all the problem sets can be solved in a second. Thus, it could be possible that the SA approach could find the solution as good as MSA if the stopping criteria (which is set to non-improving 2000 times of iterations) is extended. The simulation result of this extension indicates that SA finds solutions as good as the MSA in most of the given problem sets though the solution quality is not as stable as the MSA; the average of the objective function values were greater.

Table 1 Result comparison of SA and MSA

n / SA / MSA
ΣT / Time
(Sec.) / ΣT / Time
(Sec.)
Min / Avg / Min / Avg
20 / 934 / 986 / 0.00 / 934 / 934 / 0.17
40 / 6263 / 6284 / 0.01 / 6263 / 6263 / 0.78
60 / 5391 / 5544 / 0.03 / 5351 / 5351 / 1.00
80 / 10928 / 11107 / 0.05 / 10867 / 10912 / 2.77
100 / 50736 / 51472 / 0.11 / 50608 / 50609 / 3.94
150 / 114423 / 115376 / 0.28 / 113557 / 113559 / 10.33

In the case that we extend its stopping criteria to 200,000 non-improving iteration, the search, as mentioned above, generates solution comparible to the MSA for most of given problems. However, long search of SA can not guaretee improving solution quality.

Table 2 result comparison for 500 job scheduling

SA / MSA
ΣT / Time(Sec.) / ΣT / Time(Sec.)
781281 / 534.01 / 780539 / 540.32

The larger size of data set, n = 500, was generated to examine these heuristics as is a long procedure to schedule 500 jobs. In this case, the MSA generates more favorable solutions than that of SA. Table 2 shows the best solution generated by each approach with run-time.

6. CONCLUSION

In this paper, a modified simulated annealing approach is used for solving the single-machine mean tardiness scheduling problems. The proposed approach is compared to Ben-daya's simulated annealing approach that generates the solutions within less than 1% of optimal [1].

The result of the simulation experiment indicates that the proposed method provides more stable solutions than that of SA, and in the case of large sized problems, the proposed method provides better solutions.

Previous studies have identified the fact that the simulated annealing algorithm is not much dependent on initial sequences. MSA has this advantage and is improved by having a better direction to the solution by use of the greedy approach.

REFERENCES

[1]M. Ben-Daya and M. Al-Fawzan, A simulated annealing approach for the one-machine mean tardiness scheduling problem, European Journal of Operational Research, vol. 93, pp. 61-67, 1996.

[2] S. French. Sequencing and Scheduling: An Introduction to the Mathematics of the Job Shop, Ellis Horwood, 1982.

[3] J. Du and J. Y. T. Leung, Minimizing total tardiness on one machine is NP-hard, Mathematics of Operations Research, vol. 15, pp. 483-495, 1990.

[4] M. I. Fisher, A dual algorithm for the one-machine scheduling problem, Mathematical Programming, vol. 11, pp. 229-251, 1976.

[5] K. R. Baker, Introduction to Sequencing and Scheduling, Wiley, 1974.

[6] T. D. Fry, L. Vicens, K. Macleod, and S. Fernandez, A heuristic solution procedure to minimize T on a single machine, Journal of Operational Research Society, vol. 40, pp. 293-297, 1989.

[7] J. E. Holsenback and R. M. Russel, A heuristic algorithm for sequencing on one machine to minimize total tardiness, Journal of Operational Research Society, vol. 43, pp.53-62, 1992.

[8] C. N. Potts and L. N. Van Wassenhove, Single machine tardiness sequencing heuristic, IIE Transactions, vol. 23, no. 4, pp. 346-354, 1991.

[9] H. Emmons, One machine sequencing to minimize certain functions of job tardiness, Operations Research, vol. 17, pp. 701-715, 1969.

[10] R. W. Conway, W. L. Maxwell, and L. W. Miller, Theory of Scheduling, Addison-Wesley, 1997.

1