International IRATJ
Robotics & Automation Journal
Research Article
Volume 2 Issue 1  2017
Invasive Weed Optimization Algorithm for Minimizing Total Weighted Earliness and Tardiness Penalties on a Single Machine under Aging Effect
Maziyar Yazdani^{1}* and Reza Ghodsi^{2}
^{1}Department of Industrial Engineering, University College of Engineering, University of Tehran, Iran
^{2}Department of Engineering, Central Connecticut State University, USA
Received: October 16, 2016  Published: January 06, 2017
*Corresponding author:
Maziyar Yazdani, Department of Industrial Engineering, University College of Engineering, University of Tehran, Iran, Email:
Citation:
Yazdani M, Ghodsi R (2017) Invasive Weed Optimization Algorithm for Minimizing Total Weighted Earliness and Tardiness Penalties on a Single Machine under Aging Effect. Int Rob Auto J 2(1): 00006. DOI:
10.15406/iratj.2016.06.00006
Abstract
In this paper, minimizing total weighted tardiness and earliness criteria on a single machine is considered. Job processing time is a linear function of its starting time and each job has a distinct due date. In this study an Invasive Weed Optimization (IWO) algorithm is proposed for machine scheduling problem. Because the local search operator in IWO algorithm is designed for continuous problem only, a simple and efficient coding and decoding technique is applied to map the discrete feasible space of the permutation to a number. Then, this number is used to produce the solution. The computational results show that the performance of the proposed algorithm is much better than the GA algorithm for this problem in finding the best solutions.
Keywords: Invasive weed optimization; Single machine; Total weighted tardiness/earliness; scheduling; Stepdeterioration
Introduction
Minimizing the total weighted tardiness and earliness time on a single machine with aging effect is discussed in the research at hand and an efficient IWO algorithm is proposed for this problem. In the classical scheduling problem, processing times for different jobs are assumed to be constant within the planning horizon. However, previous researches reveal that in many scheduling environments the processing time is an increasing function of start time [1]. This phenomenon is known as aging effect which relates to many practical and industrial applications. One of the aging effect situations, which is also considered in this study, is the linear positiondependent aging effect where jobs processing time is a linear function of job’s starting time.
In recent years, most policies of modern industrial organization emphasize the need for minimizing earliness and tardiness penalty. This is more important in just in time (JIT) productions. In a JIT production environment, early job must be held in inventory until their due dates and jobs completed after their due dates can cause customer dissatisfaction, contract penalties, loss of sale and loss of reputation [2]. Therefore, many researcher pay attention to this type of scheduling. This problem is categorized as an Nphard problem [3]. Hamidinia et al. [4] proposed a genetic algorithm for minimizing total tardiness/earliness of weighted jobs in a batched delivery system [4]. A single machine scheduling problem with controllable processing times without inserted idle time to minimize total tardiness and earliness is presented by Kayvanfar et al. [5]. Kaweegitbundit developed a memetic algorithm for minimizing earliness and tardiness penalties [6] Kedad Sidhoum and Sourd proposed a neighborhood search algorithm for the single machine earlinesstardiness which jobs have distinct due dates [7]. Allaoua and Osmane proposed a new genetic algorithm inspired by the philosophy of dynamic programming, where the chromosome and the population lengths are varied from one iteration to another for earliness and tardiness problem [8]. Among the recent research in aging effect readers are referred to researches presented by [914]. No prior research has used IWO for the problem at hand.
This paper is organized as follows. In the next section, the problem considered in this study is described in more details. The proposed algorithm is presented in section 3. For evaluation of the performance of the suggested algorithm, a series of computational experiments is performed and the results of this study are reported in section 4. Finally, section 5 concludes the paper with a short summary of the work.
Problem Definition
The problem considered in this study can be formally described as follows: Assume that there are n independent jobs
$\left\{{j}_{1,}{j}_{2},\mathrm{.......}{j}_{n}\right\}$
that are available for being processed at time zero on a single machine. The machine can only process one job at a time and processing of a job cannot be interrupted until it is entirely completed (preemption is not allowed). Each job
${\text{j}}_{\text{i}}$
has a normal processing time p_{j}, a due date
${\text{d}}_{\text{j}}$
and positive weights for per unit earliness and tardiness. In addition, let
${\text{p}}_{\text{j}}$
and
${\text{p}}_{\left[\text{j}\right]}$
be the normal processing time and the actual processing time of the job scheduled in a sequence, respectively. If a job processed in rth position, actual processing time is:
${\text{p}}_{\left[\text{j}\right]}={\text{p}}_{\text{j}}+{\text{b}}_{\text{j}}\text{rforj},\text{r}=\text{}0,1,\mathrm{....},\text{n}\left(1\right)$
Where b_{j} is the aging ratio of job j?
In this problem, the objective function is minimizing the total weighted tardiness and earliness.
Proposed IWO algorithm
Main IWO algorithm
IWO is a continuous, stochastic numerical algorithm that mimics the colonizing behavior of weeds [15]. First, a population of initial seeds is randomly spread over the entire search space. These weeds will finally grow up and execute the further steps of the algorithm. There are four steps of the algorithm as below:
Initialization: A finite number of weeds are initialized randomly in the feasible search space via a uniform function.
Reproduction: Every individual in the population is permitted to produce seeds based on its own fitness as well as the colony’s lowest and highest fitness, such that the number of seeds produced by a weed increases linearly from lowest predefined possible seed for a weed with the worst fitness to the maximum number of seeds for a plant with the best fitness so far. Smin and S_{max} denote minimum and maximum number of weeds respectively and are predefined.
Spatial distribution: The generated seeds are being randomly scattered over the ddimensional search space by normally distributed random numbers with the mean equal to location of parent plant and a varying variance. This step guarantees that the produced seeds will be generated around the parent weed. However, the Standard Deviation (SD) of the random function decreases over the iterations from initial value sd_{initial} to final value sd_{final}. Standard deviation for a particular iteration is given as in equation 2 below:
${\text{sd}}_{\text{iter}}={\left(\frac{{\text{iter}}_{\text{max}}\text{iter}}{{\text{iter}}_{\text{max}}}\right)}^{\text{n}}\left({\text{sd}}_{\text{initial}}{\text{sd}}_{\text{final}}\right)+{\text{sd}}_{\text{final}}\text{}$
(2)
Where n is nonlinear modulation index. This step means that the probability of dropping a seed in the area around the parents decreases nonlinearly with iterations, which results in better plants and elimination of unsuitable plants. Hence, this is the selection mechanism of Invasive Weed Optimization Algorithm.
Competitive exclusion: When the maximum number of individual in a colony is reached (P_{max}), each weed is allowed to produce seeds and scatter them according to the mechanism indicated in the previous step. After that, parents and their new seeds are ranked together according to their fitness. Next, weeds with highest fitness are selected to reach the maximum allowable population size in a colony.
Termination condition: The entire process continues until the maximum number of iterations has been reached, and then the plant with the best fitness is the closest one to the optimal solution.
Because the IWO algorithm is designed for continues problem and the local search operator in this algorithm uses normal distribution to search the feasible space, this algorithm cannot be used directly for discrete problems without modification. Here a coding method is applied to map every permutation to a number and then use this number as the mean for the normal distribution to produce new seed (new solution). Then, using a decoding technique matches this new number to the permutation. This codingdecoding technique is described as follows.
Factoradic base
Factoradic is a specific constructed number system and a lexicographical index arrangement for permutations [16]. The concept of the factoradic is closely connected to that of the Lehmer code [16]. This numbering system is a factorialbased mixed radix numerical system: the ith digit from right side is to be multiplied by i! And the rightmost digit is always 0, the second digit is 0, or 1, the third 0, 1 or 2 and so on [16]. For instance, 44 in decimal base can be shown as
$\left({1}_{4}{3}_{3}{1}_{2}{0}_{1}{0}_{0}\right)$
in factoradic base.
$\left({1}_{4}{3}_{3}{1}_{2}{0}_{1}{0}_{0}\right)=1\times 4!\text{}+3\times 3!\text{}+1\times 2!\text{}={44}_{10}$
(3)
The factoradic numbering system never has two possible interpretations and no number can be described in more than one way due to the fact that the sum of consecutive factorials multiplied by their index is always the next factorial minus one [16]:
$\sum}_{\text{i}=0}^{\text{n}}\text{i}\times \text{i}!=\left(\text{n}+1\right)!1\text{}\left(4\right)$
Relation between factoradic base and permutations
There is a natural mapping between the permutations of n elements in lexicographical order and the integers
$0,\text{}1,\dots ,\text{}n!1,$
when the integers are expressed in factoradic form. This mapping has been called the Lehmer code. For instance, with n = 3, this mapping is illustrated in Table 1.
Decimal 
Factoradic 
Permutation 
0_{10} 
0_{2}0_{1}0_{0} 
1,2,3 
1_{10} 
0_{2}1_{1}0_{0} 
1,3,2 
2_{10} 
1_{2}0_{1}0_{0} 
2,1,3 
3_{10} 
1_{2}1_{1}0_{0} 
2,3,1 
4_{10} 
2_{2}0_{1}0_{0} 
3,1,2 
5_{10} 
2_{2}1_{1}0_{0} 
3,2,1 
Table 1: Natural mapping between factoradic numbers and permutations when n = 3.
For mapping permutations into factoradic numbers and vice versa, two algorithms are proposed in McCaffrey [17] and further used in Behroozi [18]. Computational complexity of both algorithms are O(n) which makes the algorithms able to efficiently map decimal numbers to factoradic numbers, factoradic numbers to the permutations and vice versa. These two algorithms are presented as Algorithm 1 and Algorithm 2 below.
Algorithm 1: Mapping permutation to factoradic.
 Step 1: Consider
$f=\left\{0,1,\dots ,n1\right\}$
as a list of possible digits for factoradic base in ascending order, and also a list of possible numbers in permutation
$p=\left\{1,2,\dots ,n\right\}$
 Step 2: For
$k=1,2,\dots ,n,$
select the kth digit in permutation, and find this digit in p. Suppose that this digit is the ith digit in
$p=\left\{1,2,\dots ,n\right\}$
. Choose the ith element of f, set this element as the kth element of factoradic, and omit this element from p. Table 2 demonstrates the mapping of
$\left(2\text{}\u2013\text{}3\text{}\u2013\text{}1\right)\text{}\to \text{}\left({1}_{2}{1}_{1}{0}_{0}\right)$
based on Algorithm 1.
Iteration 
k=1 
k=2 
k=3 
Permutation 
2 
3 
1 
P 
{1,2,3} 
{1,3} 
{1} 
F 
{0,1,2} 
{0,1,2} 
{0,1,2} 
Factoradic 
1 
1 
0 
Table 2: Mapping of
$\left(2\text{}\u2013\text{}3\text{}\u2013\text{}1\right)\text{}\to \text{}\left({1}_{2}{1}_{1}{0}_{0}\right)$
based on Algorithm 1.
Algorithm 2: Mapping factoradic to permutation
 Step 1: Like algorithm 1, consider a list of possible digits of factoradic base in ascending order
$f=\left\{0,1,\dots ,n1\right\}$
, and also a list of possible numbers in permutation
$p=\left\{1,2,\dots ,n\right\}$
 Step 2: For k=1,2,…,n: select the
${k}_{th}$
digit in factoradic representation, and find this digit in
$f=\left\{0,1,\dots ,n1\right\}$
. Assume that this digit is the ith digit in
$f=\left\{0,1,\dots ,n1\right\}$
. Select the
${i}_{th}$
element of p; set this element as the
${k}_{th}$
element of permutation, and omit this element from p. Table 3 demonstrates the mapping of
$\left({1}_{2}{1}_{1}{0}_{0}\right)\text{}\to \text{}\left(2\text{}\u2013\text{}3\text{}\u2013\text{}1\right)$
based on Algorithm 2.
Iteration 
k=1 
k=2 
k=3 
Factoradic 
1 
1 
0 
F 
{0,1,2} 
{0,1,2} 
{0,1,2} 
P 
{1,2,3} 
{1,3} 
{1} 
Permutation 
2 
3 
1 
Table 3: Mapping of
$\left({1}_{2}{1}_{1}{0}_{0}\right)$
$\to $
$\left(2\text{}\u2013\text{}3\text{}\u2013\text{}1\right)$
based on Algorithm 2.
Proposed IWO algorithm
 Step 1: Set the values of the control parameters:
${N}_{int}$
(number of initial seed),
${P}_{max}$
(maximum number of plant can be survived in every iteration),
$ite{r}_{max}$
(maximum number of iterations),
${S}_{max}$
(maximum number of seed that a plant can produced according to that’s fitness), Smin (minimum number of seed that a plant can produced according to that’s fitness), n (nonlinear modulation index),
$s{d}_{initial}$
(initial value of standard deviation), and
$s{d}_{final}$
(final value of standard deviation).
 Step 2: Generate initial solutions (initial seeds’ population) to initiate solution space exploration. For single machine problem with n jobs, any permutation of n number can be a feasible initial solution for problem.
 Step 3: This step is the fitness evaluation of each seed. Calculate the values of the fitness functions for the solutions according to objective function. The seed is called a plant after assigning each fitness value to the corresponding seed.
 Step 4: Rank the plants and plants reproduce new seeds. Plants are ranked according to the corresponding fitness values. Plants generate seeds based on the rank in the colony. The number of new seeds to be produced is computed for each plant using the linear relationship considering
${\text{S}}_{\text{min}}$
and
${\text{S}}_{\text{max}}$
.
 Step 5: Spread the newly produced seeds. The produced seeds are spread over the search area based on the standard deviation of each step. Because this algorithm uses normal distribution to spread newly produced seed, factoridc coding is applied to map jobs permutation to a number and by using that number as the mean of normal distribution the new seed is spread.
 Step 6: Compute the fitness values of the new plants.
 Step 7: Is the number of the plants in the current step less than maximum number of plant?
Yes: Go to step 9.
No: Then do competitive exclusion. In proposed algorithm, k% of the plants with better fitness values is selected and other population of next iteration is selected randomly through remaining plants.
 Step 8: Run the intensification procedure. Intensification is the search in the neighborhood of the current solutions for constructing better solutions closer to optimum solution. This is done by switching the positions of the first two jobs and then, the objective function value of this new permutation is calculated. If the objective function of the new switched permutation is better, the algorithm records this switch and its objective function value. Next, two jobs will move back to their original position before switching. Next, the position of the first job and the third job are switched. This procedure continues and is applied for the first job and all other jobs and finally the switch with the most improvement in objective function value is accepted. The same procedure is applied for job two in the new position and all jobs after second position. Thus, these steps are repeated for job in position one to job in position n1.
In this proposed IWO algorithm, the described procedures is applied to q% of the population in every iteration randomly.
 Step 9: Is the iteration number less than maximum number of iteration?
Yes: Repeat the algorithm again.
No: Stop. Calculate the objective function values of the current plants and choose the best among them.
Computational Results
In this section, the performance of the proposed IWO is presented. Problems with different sizes are considered. The small size problems are associated with 10 jobs, medium size with 15 and 20 jobs, and large size with 40 and 60 jobs. The processing times are generated from the discrete uniform distribution [40,120] and weight of earliness–tardiness penalties are drawn from the discrete uniform distribution [1, 4]. The aging ratio of each job is drawn from the uniform distribution [0, 2] and the due dates of each job is drawn from the uniform distribution
$\left[dmin\lambda ,\text{}dmin+\lambda \right],$
where
$dmin=P(1TEF),\text{P}=\left({\displaystyle \sum}_{\text{i}=1}^{\text{n}}{\text{p}}_{\text{i}}\right)+(\frac{\text{n}}{2}\times {\displaystyle \sum}_{\text{i}=1}^{\text{n}}{\text{b}}_{\text{i}}$
and
$\lambda =P\left(RDD/2\right)$
.
The two parameters RDD and TEF are the relative range of due dates and tardiness/earliness function, respectively. RDD gets the values of 0.2 and 0.5. Also TEF gets the values of 0.2 and 0.35. Table 4 shows the generated problems.
Number of Jobs 
TEF = 0.35 
TEF = 0.2 
RDD = 0.2 
RDD = 0.5 



10 
J101 
J102 
15 
J151 
J152 
20 
J201 
J202 
40 
J401 
J402 
60 
J601 
J602 
Table 4: Name of problems generated with variable parameters obtained is shown in Table 5.
The following experimentally derived values are proposed for the parameters:
$\text{Nint}=\text{n},\text{Pmax}=\text{n},\text{itermax}=5\times \text{n},\text{Smax}=3,\text{Smin}=1,\text{n}=2,\text{sdinitial}={\text{n}}^{2},\text{sdfinal}=2,k=10\%$
and
$q=5\%$
. And n is the number of jobs.
The proposed algorithm is evaluated against the Genetic Algorithm (GA), GA parameters are as below:
Number of initial population=50, crossover operator: uniform (80%), mutation operator: Inversion (0.02), selection operator: roulette wheel. stop condition: 10n.
For each instance both algorithms run five times independently and best and worst solutions obtained are shown in Table 5.
Problem Name 
Number of Jobs 
GA 


IWO 


Best 
Average 
Worst 
Best 
Average 
Worst 
J101 
10 
4916 
4916 
4916 
4916 
4916 
4916 
J102 
10 
5515 
5515 
5515 
5515 
5515 
5515 
J151 
15 
11081 
11104.6 
11127 
11081 
11081 
11081 
J152 
15 
17169 
17190.6 
17227 
17169 
17169.8 
17171 
J201 
20 
25901 
25949.2 
25981 
25901 
25901 
25901 
J202 
20 
31598 
31621.8 
31647 
31581 
31581 
31581 
J401 
40 
97783 
97927.2 
98026 
97135 
97139.8 
97159 
J402 
40 
128239 
128322 
128461 
127989 
127990.8 
127995 
J601 
60 
249017 
249757.8 
250785 
247707 
247987 
248057 
J602 
60 
202926 
203481 
204003 
201689 
201702.2 
201711 
Table 5: Compare best, mean and worst solutions that obtained for algorithms.
In addition, to compare the two methods, Relative Percentage Deviation (RPD) is used, which is computed in the following way:
$\text{PRD}=\frac{{\text{alg}}_{\text{sol}}{\text{min}}_{\text{sol}}}{{\text{min}}_{\text{sol}}}\text{}$
(5)
Where
${\text{Alg}}_{\text{sol}}\text{}$
as the objective function value is obtained for a given algorithm and Minsol is the best solution obtained for each instance by any of the two algorithms. Figure 1 compares the mean of PRD for the two algorithms. The computational results show that the proposed IWO has less deviation from the best solution and that the algorithm is more promising in finding nearoptimum solutions.
Figure 1: Mean of PRD for two algorithms in 5 run.
Conclusion
This research considered the single machine scheduling problem where the processing time of jobs depends on the position of the job scheduled. This problem is NPhard and finding optimum solution for the large instances of this problem is not possible in a reasonable time. An Invasive Weed Optimization Algorithm was proposed to find nearoptimal solutions for this problem. The proposed algorithm employs a coding procedure to map the permutation of jobs into a continuous space where Invasive Weed Optimization Algorithm can efficiently spread the new produced seed sand perform exploration. Afterward, the algorithm maps the new seed to a permutation. Moreover, a powerful intensification subalgorithm was applied to search the promising areas of the feasible space more comprehensively. Performance of the proposed algorithm was tested using several generated problems and compared to GA algorithm. The computational results prove that the proposed algorithm is more promising than the GA algorithm used.
References
 Pinedo M (1995) Scheduling: Theory, Algorithms and Systems. Springer.
 Liao CJ, Cheng CC (2007) A variable neighborhood search for minimizing single machine weighted earliness and tardiness with common due date. Computers and Industrial Engineering 52(4): 404413.
 Liao CJ, Choi JY (1995) A genetic algorithm for job sequencing problems with distinct due dates and general earlytardy penalty weights. Computers and Operations Research 22(8): 857869.
 Hamidinia A (2012) A genetic algorithm for minimizing total tardiness/earliness of weighted jobs in a batched delivery system. Computers and Industrial Engineering 62(1): 2938.
 Kayvanfar V I, Mahdavi, Komaki GM (2011) Single machine scheduling with controllable processing times to minimize total tardiness and earliness. Computers and Industrial Engineering 65(1): 166175.
 Kaweegitbundit P (2011) A Single Machine Scheduling Problem with Earliness and Tardiness Penalties Using Memetic Algorithm. Advanced Materials Research 314: 23532357.
 KedadSidhoum S, Sourd F (2010) Fast neighborhood search for the single machine earlinesstardiness scheduling problem. Computers and Operations Research 37(8): 14641471.
 Allaoua H, Osmane I (2010) Variable parameters lengths genetic algorithm for minimizing earlinesstardiness penalties of single machine scheduling with a common due date. Electronic Notes in Discrete Mathematics 36(C): 471478.
 Fan J, Xu D (2010) Some singlemachine scheduling problems with aging effect. IEEE Explore.
 Janiak A, Rudek R (2010) Scheduling jobs under an aging effect. Journal of the Operational Research Society 61(6): 10411048.
 Ji M, Hsu CJ, Yang DL (2011) Singlemachine scheduling with deteriorating jobs and aging effects under an optional maintenance activity consideration. Journal of Combinatorial Optimization 26(3): 437447.
 Rudek R (2012) Some singlemachine scheduling problems with the extended sumofprocessingtimebased aging effect. International Journal of Advanced Manufacturing Technology 59(14): 299309.
 Rudek R (2012) The strong NPhardness of the maximum lateness minimization scheduling problem with the processingtime based aging effect. Applied Mathematics and Computation 218(11): 64986510.
 Yang SJ, Yang DL (2010) Minimizing the makespan on singlemachine scheduling with aging effect and variable maintenance activities. Omega 38(6): 528533.
 Mehrabian AR Lucas C (2006) A novel numerical optimization algorithm inspired from weed colonization. Ecological Informatics 1(4): 355366.
 Knuth DE (1973) Seminumerical algorithms. (3rd edn), The Art of Computer Programming, AddisonWesley Longman Publishing Co Boston, MA, USA.
 McCaffrey J (2003) Using permutations. NET for improved systems security.
 Behroozi M (2009) A metaheuristic approach for a special class of job shop scheduling problem. Faculty of industrial engineering. Tehran, Sharif University of Technology, Iran.

