Parallel robot scheduling to minimize mean tardiness with precedence constraints using a genetic algorithm

https://doi.org/10.1016/j.advengsoft.2006.11.003Get rights and content

Abstract

Identical parallel robot scheduling problem for minimizing mean tardiness with precedence constraints is a very important scheduling problem. But, the solution of this problem becomes much difficult when there are a number of robots, jobs and precedence constraints. Genetic algorithm is an efficient tool in the solution of combinatorial optimization problems, as it is well known. In this study, a genetic algorithm is used to schedule jobs that have precedence constraints minimizing the mean tardiness on identical parallel robots. The solutions of problems, which have been taken in different scales, have been done using simulated annealing and genetic algorithm. In particular, genetic algorithm is found noteworthy successful in large-scale problems.

Introduction

In this study, a genetic algorithm is used to schedule jobs that have precedence constraints minimizing the mean tardiness on n-number of job and m-number of identical parallel robots. There are many algorithms and heuristics related to the scheduling problem of parallel machines and robots. In this study, a genetic algorithm has been used to find the job schedule, which minimizes the mean tardiness. We know that this problem is in the class of NP-hard combinatorial problem.

Kashara and Narita [1] developed a heuristic algorithm and optimization algorithm for parallel processing of robot arm control computation on a multiprocessor system. Chen et al. [2] developed a state-space search algorithm coupled with a heuristic for robot inverse dynamics computation on a multiprocessor system. An assignment rule noted traffic priority index (TPI) was built in 1991 by Ho and Chang [3]. In this method, SPT and EDD rules are combined using by using a new measurement named as traffic congestion ratio (TCR). Then, for the cases with one or identical machine they built heuristics. Their heuristics consist of building a first solution by scheduling jobs in increasing order of their priority index. Then they improved this solution using permutation technique of WI method, which was developed previously by Wilkerson and Irwin [4].

Koulamas [5] developed a heuristic noted hybrid simulated annealing (HAS) based on simulated annealing. Chen et al. [6] have developed highest priority job first (HPJF) method, which is based on extension of the WI method extended with various priority rules such as minimum processing time first (priority = 1/processing time), maximum processing time first (priorıty = processing time), minimum deadline first (priority = 1/due date) and maximum deadline first (priority = due date). Alidaee and Rosa [7], in 1997, proposed a heuristic which is based on extending the modified due date (MDD) method belonging Baker and Bertrand [8]. Their method is quite effective for parallel machine problem according to their reports. Azizoglu and Kirca [9] proposed a branch and bound (BAB) approach to solve the same problem mentioned in this paper. Another example can be given by considering identical due dates and processing times, Elmaghraby and Park in 1974 [10], developed an algorithm based on a branch and bound to minimize a function of penalties belonging to tardiness. In 1977, Barnes and Brennan [11] evaluated and improved their method again.

In addition to these previous studies, there are a few more studies, which deal with parallel machine scheduling problem. But these studies are interested in alternatives. A few examples are given in the following for the minimization of the total weighted tardiness: Emmons and Pinedo [12], Arkin and Roundy [13]; for uniform or unspecified parallel machines scheduling, the example studies are: Emmons [14] or Guinet [15]. Karp [16] has shown that even the total tardiness minimization in two identical machine scheduling problem was NP-hard. A branch and bound algorithm to minimize maximum lateness considering due dates, family setup times and release dates has been presented by Shutten and Leussink [17]. A genetic algorithm was used to find a scheduling policy for identical parallel machine with setup times in Tamimi and Rajan’s study [18]. Armento Yamashita [19] applied tabu search into parallel machine scheduling. A scheduling problem for unrelated parallel machine with sequence dependent setup times was studied by Kim et al. [20] using simulated annealing. SA was used to determine a scheduling policy to minimize total tardiness. Min and Cheng [21] proposed an algorithm for identical parallel machine problem. Their algorithm is based on using GA and SA to minimize makespan. According to their studies, it is seen that GA proposed is efficient and fit for larger scale identical machine scheduling problem to minimize the makespan. Kanjo and Ase [22] studied about scheduling in a multi robot welding system. Sun and Zhu [23] applied a genetic algorithm for scheduling dual resources with robots. Zacharia and Asparagatos [24] proposed a method on GAs for optimal robot task scheduling. In this study, the job with n-number of precedence constraints is assigned minimizing mean tardiness on m-number of parallel robot using genetic algorithms. A sample work station of robots working in parallel is shown in Fig. 1.

Section snippets

Definition of the problem

In this study, the job with n-number of precedence constraints is scheduled minimizing mean tardiness on m-number of parallel robots. There are process time and due date for each job. There is not any ready time that belongs to jobs. A robot can do just one job at the same time. The processing is non-preemptive. The target function, which will be minimized, is given below in Eq. (1).Mean Tardiness=i=1mj=1nR(i,j)TjnHere, Tj = max{0, Cj  dj} is the tardiness of job j. Cj being the completion time

Genetic algorithm

The advantages of the genetic algorithms have been mentioned in the previous section. In this section, the modeling and the application of the GA are explained. From the view point of the working principle, genetic algorithms firstly needs the coding of the problem with the condition that it should be fitting with the GA. After coding process, GA operators are applied on chromosomes. It is not guaranteed that the obtained new offsprings are good solutions by the working of crossover and

Simulated annealing

In this study, two operators have been used in the application of SA. The first operator is that a randomly selected job has been swapped with another job, which is on the same level, and then, a new offspring has been obtained. The second operator is that a randomly selected job has been again swapped with another job and then, a new solution alternative has been obtained. If these obtained solution alternatives are valid, they are taken into consideration. Used first operator does the same

Comparison of GA and SA

GA and SA are not much different algorithms; theoretically, both of them are quite relative algorithms. However, their formulations are done using very different terminology. In a problem solution with SA, the costs, neighbors and moves of the solutions are talked (discussed), however, in a problem solution with GA, one discusses about chromosomes, their crossover, fitness and mutation. Another difference; a chromosome is considered as a genotype, which only indicates a solution. This is a

Example problem

As another example, a parallel robot problem with 12 jobs and 2 parallel robots was taken under consideration below. The process times, delivery times and precedence constraints of jobs were given. The solution, which minimizes mean tardiness, was obtained by considering these data. The problem was solved by using SPT, EDD, SA and GA. The data and the results were given below. In Table 1, the jobs with process and due dates belonging to them were given. The precedence constraints of the jobs

Computational experimentation

The number of jobs used in the problems in this study were given in Table 3 In this table, i denotes the jobs and pi is an integer processing time and wi is an integer weight, which were generated from two uniform distributions. The function of [1, 10] and [1, 100] are to create low or high variations, respectively. TF, which is the relative range of due dates, RDD and Average tardiness factor, were selected from the set [0.1, 0.3, 0.5, 0.7, 0.9]. Here, di is an integer due date from the uniform

Conclusions

The genetic algorithms (GA) have the great advantage and success in the solution of NP problems. There are various important applications on this way. In this study, the job with n-number of precedence constraints is assigned minimizing mean tardiness on m-number of parallel robot. Genetic algorithms and simulated annealing methods were used to find the solutions, which minimizes the mean tardiness. In GA, the solution alternatives, which were obtained by using genetic operators, were

References (24)

  • C. Koulamas

    Decomposition and hybris simulated annealing heuristics for the parallel machine total tardiness problem

    Nav Res Log

    (1997)
  • Chen K, Wong JS, Ho JC, A heuristic algorithm to minimize tardiness for parallel machines. In: Proceedings of ISMM⧹...
  • Cited by (0)

    View full text