A hybrid algorithm to minimize the number of tardy jobs in single machine scheduling.

Bancila, Daniel ; Buzatu, Constantin

1. INTRODUCTION

This study regards the general problem of scheduling on a single machine, denoted by 1 [absolute value of [r.sub.j]] [SIGMA] [U.sub.j]. A set of n jobs needs to be scheduled on one machine, the processing cannot be interrupted, there are no precedence relations among jobs and only one job can be processed at a time. Each job [J.sub.j] has a release time [r.sub.j], needs [p.sub.j] time units to be processed on the machine and must be completed until the due time [d.sub.j]. The starting time of a job is denoted by [t.sub.j] ([t.sub.j] [greater than or equal to] [r.sub.j]) and the completion time by [C.sub.j] ([C.sub.j] = [t.sub.j] + [p.sub.j]). If the [J.sub.j] job is completed after its due date ([C.sub.j] > [d.sub.j] => [U.sub.j] = 1) it is said to be late. Otherwise, if [C.sub.j] [less than or equal to] [d.sub.j], the job is on time. Thus, our objective is to minimize the number of late jobs ([SIGMA] [U.sub.j]).

In literature, this problem is considered to be NP-hard, series of solving methods being proposed over time.

In (Dauzere-Peres & Sevaux, 2004) the authors solve this problem by developing a branch-and-bound method. This algorithm defines a "master sequence" by using dominant rules.

In (Crauwels et al., 2005) the same problem is also treated by branch-and-bound techniques, but the jobs are grouped into families. A two alternative branching schemes is proposed.

The two methods presented above have a highly degree of efficiency in the case of small problems. However, in the case of more complex problems the computational time increases, making them impossible to be solved.

In (Gelinas & Soumis, 1997) is presented the scheduling problem on a single machine having as objective the minimization of completion time of all jobs. In this case the authors used the dynamic programming in order to solve the problem.

(Vakhania, 2004) solved the same problem by the means of an algorithm called "balancing procedure", which used the GT heuristic.

In the last years, more and more interest gained the suboptimal methods, among these the genetic algorithms being frequently used.

In (Sevaux & Sorensen, 2004), is presented a genetic algorithm applied on a Just In Time scheduling, while in (Miller et al., 1999) the genetic algorithm is combined with an Wagner-Whitin algorithm and with TSP modeling.

Taking into consideration the fact that genetic algorithms have better results in shorter time we developed a hybrid genetic algorithm in order to solve our problem. In the next section the used hybrid algorithm will be described.

2. THE HYBRID ALGORITHM

The proposed hybrid algorithm (H.A.) (Fig. 1) is based on the fundamentals of genetic algorithms, being modified according to the following steps:

1. Generate an initial population;

2. Produce a new generation P;

3. Invert the new obtained generation to produce InvP generation;

4. Evaluate the objective function for both P and InvP generations;

5. Choose from P and InvP the best n individuals to form the next generation (n--number of individuals from a generation);

6. Repeat steps 2-5 until the prescribed stop criterion is satisfied.

[FIGURE 1 OMITTED]

3. COMPUTATIONAL RESULTS AND COMPARISON

In this section we will discuss the computational results of the hybrid algorithm in the case of single machine scheduling. In order to properly compare the performances of a standard GA and the HA, we applied both algorithms on several scheduling problems, a simple case being outlined in the following section.

The problem consists of seven jobs which have to be scheduled on a single machine. The release, processing and due time for each job are given in Table 1.

When comparing their performance, the HA and GA have the same population size, consisting of six individuals, the genetic operators are the same in both methods, and the number of generations is set to 60. The results of one sample are illustrated in fig. 2 and fig.3.

[FIGURE 2 OMITTED]

From fig. 2 it is shown that the HA improves much faster than the GA, which is an advantageous feature of the HA. In addition, the execution time for the HA is almost the same as the GA. The time spent on inverting procedure in negligible.

[FIGURE 3 OMITTED]

As seen in fig. 3 the number of tardy jobs obtained by applying HA to our problem is smaller than in the case of GA. The two optimal solutions generated by applying HA and GA on our problem become:

1 [right arrow] 3 [right arrow] 4 [right arrow] 5 [right arrow] 6 [right arrow] 7 [right arrow] 2 (generated with HA); 1 [right arrow] 3 [right arrow] 5 [right arrow] 6 [right arrow] 7 [right arrow] 2 [right arrow] 4 (generated with Ga).

By applying active-decoding procedure on these two solutions we obtained the two Gantt diagrams in fig. 4 and fig. 5.

[FIGURE 4 OMITTED]

[FIGURE 5 OMITTED]

4. CONCLUSIONS

A hybrid algorithm based on an integration of a genetic algorithm and heuristic rules is proposed in this paper in order to solve the problem of minimizing the number of tardy jobs in single machine scheduling. The most prominent feature of our algorithm is a combination of heuristic rules (used to generate the initial individuals) with genetic operators to generate new individuals, which can effectively guide and speed up the genetic search. Another characteristic of the algorithm is consisted in the way the next generation is formed, by using the inverted generation, greatly increasing the flexibility of the algorithm. We have compared the hybrid algorithm HA to a standard genetic algorithm GA and the computational results showed that our algorithm is superior to the GA.

As a future research, by combining the presented algorithm with other scheduling methods like: linear programming, simple and complex heuristic rules, branch & bound techniques, other space search methods or even artificial intelligence, new algorithms for solving different problems like scheduling on parallel machines or the generalized job shop scheduling, can be obtained.

5. REFERENCES

Buzatu, C.; Bancila, D. (2008). A Hybrid Algorithm for Job Shop Scheduling, Proceedings of the 6h International Conference of DAAAM Baltic Industrial Engineering, Kyttner, R., pp. 309-314, ISBN 978-9985-59-783-5, Tallinn, April 2008, Tallinn University of Technology, Tallinn

Crauwels, H.A.J.; Potts, C.N.; Van Oudheusden, D.; Van Wassenhove, L.N. (2005). Branch and Bound Algorithms for Single Machine Scheduling with Batching to Minimize the Number of Late Jobs. Journal of Scheduling, Vol. 8, (2005) pp. 161-177

Dauzere-Peres, S.; Sevaux, M. (2004). An Exact Method to Minimize the Number of Tardy Jobs in Single Machine Scheduling. Journal of Scheduling, Vol. 7, (2004) pp. 405-420

Gelinas, S.; Soumis, F. (1997). A Dynamic Programming Algorithm for Single Machine Scheduling with Ready Times. Annals of operations research, Vol. 69, (1997) pp. 135-156

Miller, D.; Chen, H.; Matson, J.; Liu, Q. (1999). A Hybrid Genetic Algorithm for the Single Machine Scheduling Problem. Journal of Heuristics, Vol. 5, (1999) pp. 437-454

Sevaux, M.; Sorensen, K. (2004). A Genetic Algorithm for Robust Schedules in a One-Machine Environment with Ready Times and Due Dates. Quarterly Journal of the Belgian, French and Italian Operations Research Societies, Vol. 2, (2004) pp. 129-147

Vakhania, N. (2004). Single-Machine Scheduling with Release Times and Tails. Annals of Operations Research, Vol. 129, (2004) pp. 253-271.

Table 1. Release, processing and due time for each job

J 1 2 3 4 5 6 7

[r.sub.j] 0 2 4 5 7 11 18
[p.sub.j] 3 5 2 1 7 6 3
[d.sub.j] 4 7 9 8 18 22 27