Parallel robot scheduling to minimize mean tardiness with precedence constraints using a genetic algorithm
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).Here, 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)
- et al.
Scheduling parallel machines to weighted and un-weight tardiness
Comput Oper Res
(1997) - et al.
A dynamic priority rule for sequencing against due-date
J Oper Manage
(1982) - et al.
Tardiness minimization on parallel machines
Int J Prod Econ
(1998) - et al.
Scheduling stochastic jobs, with due dates on parallel machines
Eur J Oper Res
(1990) - et al.
Parallel Machine scheduling with release dates, and family setup times
Int J Prod Econ
(1996) - et al.
Optimal robot task scheduling based on genetic algorithms
Robot Comput Integr Manuf
(2005) - et al.
Parallel processing of robot arm control computation on a multimicroprocessor system
IEEE J Robotic Autom
(1985) - et al.
Efficient scheduling Algorithm algorithms for robot inverse dynamics computation on a multiprocessor system
IEEE Trans Syst, Man, Cybernet
(1988) - et al.
Heuristics for minimizing mean tardiness for m parallel machines
Nav Res Log
(1991) - et al.
An improved algorithm for scheduling independent jobs
AIIE Trans
(1971)