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 Yazdani1* and Reza Ghodsi2
1Department of Industrial Engineering, University College of Engineering, University of Tehran, Iran
2Department 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; Step-deterioration

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 position-dependent 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 Np-hard 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 earliness-tardiness 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 [9-14]. 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 { j 1, j 2 ,....... j n } MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfa4aaiWaae aacaWGQbWaaSbaaKqbGeaacaaIXaGaaiilaaqcfayabaGaamOAamaa BaaajuaibaGaaGOmaaqcfayabaGaaiilaiaac6cacaGGUaGaaiOlai aac6cacaGGUaGaaiOlaiaac6cacaWGQbWaaSbaaKqbGeaacaWGUbaa juaGbeaaaiaawUhacaGL9baaaaa@46C1@ 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 j i MathType@MTEF@5@5@+= feaagKart1ev2aqatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaieaaaaaa aaa8qacaqGQbWdamaaBaaajuaibaWdbiaabMgaa8aabeaaaaa@38FB@ has a normal processing time pj, a due date d j MathType@MTEF@5@5@+= feaagKart1ev2aqatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaieaaaaaa aaa8qacaqGKbWdamaaBaaajuaibaWdbiaabQgaaKqba+aabeaaaaa@3984@ and positive weights for per unit earliness and tardiness. In addition, let p j MathType@MTEF@5@5@+= feaagKart1ev2aqatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaieaaaaaa aaa8qacaqGWbWdamaaBaaajuaibaWdbiaabQgaa8aabeaaaaa@3902@  and p [ j ] MathType@MTEF@5@5@+= feaagKart1ev2aqatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaieaaaaaa aaa8qacaqGWbWdamaaBaaajuaibaqcfa4dbmaadmaajuaipaqaa8qa caqGQbaacaGLBbGaayzxaaaapaqabaaaaa@3BCF@ 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:

p [ j ] = p j + b j r for j,= 0,1,....,( 1 ) MathType@MTEF@5@5@+= feaagKart1ev2aqatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaieaaaaaa aaa8qacaqGWbWdamaaBaaajqwba+FaaKqba+qadaWadaqcKvaG==aa baWdbiaabQgaaiaawUfacaGLDbaaa8aabeaajuaGpeGaeyypa0Jaae iCa8aadaWgaaqcfasaa8qacaqGQbaajuaGpaqabaWdbiabgUcaRiaa bkgapaWaaSbaaKqbGeaapeGaaeOAaaWdaeqaa8qacaqGYbqcfaOaae iOaiaabAgacaqGVbGaaeOCaiaabckacaqGQbGaaiilaiaabkhacaqG GcGaeyypa0JaaeiOaiaaicdacaGGSaGaaGymaiaacYcacaGGUaGaai Olaiaac6cacaGGUaGaaiilaiaab6gacaqGGcWaaeWaa8aabaWdbiaa igdaaiaawIcacaGLPaaaaaa@5E70@

Where bj 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 Smax denote minimum and maximum number of weeds respectively and are predefined.

Spatial distribution: The generated seeds are being randomly scattered over the d-dimensional 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 sdinitial to final value sdfinal. Standard deviation for a particular iteration is given as in equation 2 below:

sd iter = ( iter max iter iter max ) n ( sd initial sd final )+ sd final     MathType@MTEF@5@5@+= feaagKart1ev2aqatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaieaaaaaa aaa8qacaqGZbGaaeiza8aadaWgaaqcfasaa8qacaqGPbGaaeiDaiaa bwgacaqGYbaajuaGpaqabaWdbiabg2da9maabmaapaqaa8qadaWcaa WdaeaapeGaaeyAaiaabshacaqGLbGaaeOCa8aadaWgaaqcfasaa8qa caqGTbGaaeyyaiaabIhaa8aabeaajuaGpeGaeyOeI0IaaeyAaiaabs hacaqGLbGaaeOCaaWdaeaapeGaaeyAaiaabshacaqGLbGaaeOCa8aa daWgaaqcfasaa8qacaqGTbGaaeyyaiaabIhaaKqba+aabeaaaaaape GaayjkaiaawMcaa8aadaahaaqabKqbGeaapeGaaeOBaaaajuaGdaqa daWdaeaapeGaae4CaiaabsgapaWaaSbaaKqbGeaapeGaaeyAaiaab6 gacaqGPbGaaeiDaiaabMgacaqGHbGaaeiBaaqcfa4daeqaa8qacqGH sislcaqGZbGaaeiza8aadaWgaaqcfasaa8qacaqGMbGaaeyAaiaab6 gacaqGHbGaaeiBaaqcfa4daeqaaaWdbiaawIcacaGLPaaacqGHRaWk caqGZbGaaeiza8aadaWgaaqcfasaa8qacaqGMbGaaeyAaiaab6gaca qGHbGaaeiBaiaabckaaKqba+aabeaapeGaaeiOaiaabccaaaa@7541@  (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 (Pmax), 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 coding-decoding 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 factorial-based 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 ( 1 4 3 3 1 2 0 1 0 0 ) MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfa4aaeWaae aaqaaaaaaaaaWdbiaaigdapaWaaSbaaKqbGeaapeGaaGinaaWdaeqa aKqba+qacaaIZaWdamaaBaaajuaibaWdbiaaiodaaKqba+aabeaape GaaGyma8aadaWgaaqcfasaa8qacaaIYaaajuaGpaqabaWdbiaaicda paWaaSbaaKqbGeaapeGaaGymaaqcfa4daeqaa8qacaaIWaWdamaaBa aajuaibaWdbiaaicdaaKqba+aabeaaaiaawIcacaGLPaaaaaa@44F7@ in factoradic base.

( 1 4 3 3 1 2 0 1 0 0 )=1×4! +3×3! +1×2! = 44 10 MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfa4aaeWaae aaqaaaaaaaaaWdbiaaigdapaWaaSbaaKqbGeaapeGaaGinaaWdaeqa aKqba+qacaaIZaWdamaaBaaajuaibaWdbiaaiodaaKqba+aabeaape GaaGyma8aadaWgaaqcfasaa8qacaaIYaaajuaGpaqabaWdbiaaicda paWaaSbaaKqbGeaapeGaaGymaaqcfa4daeqaa8qacaaIWaWdamaaBa aajuaibaWdbiaaicdaaKqba+aabeaaaiaawIcacaGLPaaapeGaeyyp a0JaaGymaiabgEna0kaaisdacaGGHaGaaeiiaiabgUcaRiaaiodacq GHxdaTcaaIZaGaaiyiaiaabccacqGHRaWkcaaIXaGaey41aqRaaGOm aiaacgcacaqGGaGaeyypa0JaaGinaiaaisdapaWaaSbaaKqbGeaape GaaGymaiaaicdaaKqba+aabeaaaaa@5B5A@ (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]:

i=0 n ×i!=( n+1 )!1 ( 4 ) MathType@MTEF@5@5@+= feaagKart1ev2aqatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaieaaaaaa aaa8qadaGfWbqabKqbG8aabaWdbiaabMgacqGH9aqpcaaIWaaapaqa a8qacaqGUbaajuaGpaqaa8qacqGHris5aaGaaeyAaiaabckacqGHxd aTcaqGPbGaaiyiaiabg2da9maabmaapaqaa8qacaqGUbGaey4kaSIa aGymaaGaayjkaiaawMcaaiaacgcacqGHsislcaaIXaGaaeiOamaabm aapaqaa8qacaaI0aaacaGLOaGaayzkaaaaaa@4E56@

Relation between factoradic base and permutations

There is a natural mapping between the permutations of n elements in lexicographical order and the integers 0, 1,, n!1, MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaieaaaaaa aaa8qacaaIWaGaaiilaiaabccacaaIXaGaaiilaiabgAci8kaacYca caqGGaGaamOBaiaacgcacqGHsislcaaIXaGaaiilaaaa@40ED@ 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

010

020100

1,2,3

110

021100

1,3,2

210

120100

2,1,3

310

121100

2,3,1

410

220100

3,1,2

510

221100

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.

  1. Step 1: Consider f={ 0,1,,n1 } MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaieaaaaaa aaa8qacaWGMbGaeyypa0ZdamaacmaabaWdbiaaicdacaGGSaGaaGym aiaacYcacqGHMacVcaGGSaGaamOBaiabgkHiTiaaigdaa8aacaGL7b GaayzFaaaaaa@42A2@ as a list of possible digits for factoradic base in ascending order, and also a list of possible numbers in permutation p={ 1,2,,n } MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaieaaaaaa aaa8qacaWGWbGaeyypa0ZdamaacmaabaWdbiaaigdacaGGSaGaaGOm aiaacYcacqGHMacVcaGGSaGaamOBaaWdaiaawUhacaGL9baaaaa@4106@
  2. Step 2: For k=1,2,,n, MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaieaaaaaa aaa8qacaWGRbGaeyypa0JaaGymaiaacYcacaaIYaGaaiilaiabgAci 8kaacYcacaWGUbGaaiilaaaa@3F52@ select the kth digit in permutation, and find this digit in p. Suppose that this digit is the ith digit in p={ 1,2,,n } MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaieaaaaaa aaa8qacaWGWbGaeyypa0ZdamaacmaabaWdbiaaigdacaGGSaGaaGOm aiaacYcacqGHMacVcaGGSaGaamOBaaWdaiaawUhacaGL9baaaaa@4106@ . 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 ( 2  3  1 )  ( 1 2 1 1 0 0 ) MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfa4aaeWaae aaqaaaaaaaaaWdbiaaikdacaqGGaGaai4eGiaabccacaaIZaGaaeii aiaacobicaqGGaGaaGymaaWdaiaawIcacaGLPaaapeGaaeiiaiabgk ziUkaabccapaWaaeWaaeaapeGaaGyma8aadaWgaaqcfasaa8qacaaI YaaajuaGpaqabaWdbiaaigdapaWaaSbaaKqbGeaapeGaaGymaaqcfa 4daeqaa8qacaaIWaWdamaaBaaajuaibaWdbiaaicdaaKqba+aabeaa aiaawIcacaGLPaaaaaa@4AF7@  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 ( 2  3  1 )  ( 1 2 1 1 0 0 )  MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfa4aaeWaae aaqaaaaaaaaaWdbiaaikdacaqGGaGaai4eGiaabccacaaIZaGaaeii aiaacobicaqGGaGaaGymaaWdaiaawIcacaGLPaaapeGaaeiiaiabgk ziUkaabccapaWaaeWaaeaapeGaaGyma8aadaWgaaqcfasaa8qacaaI YaaajuaGpaqabaWdbiaaigdapaWaaSbaaKqbGeaapeGaaGymaaqcfa 4daeqaa8qacaaIWaWdamaaBaaajuaibaWdbiaaicdaaKqba+aabeaa aiaawIcacaGLPaaapeGaaiiOaaaa@4C2B@ based on Algorithm 1.

Algorithm 2: Mapping factoradic to permutation

  1. Step 1: Like algorithm 1, consider a list of possible digits of factoradic base in ascending order f={ 0,1,,n1 } MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaieaaaaaa aaa8qacaWGMbGaeyypa0ZdamaacmaabaWdbiaaicdacaGGSaGaaGym aiaacYcacqGHMacVcaGGSaGaamOBaiabgkHiTiaaigdaa8aacaGL7b GaayzFaaaaaa@42A2@ , and also a list of possible numbers in permutation   p={ 1,2,,n } MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaieaaaaaa aaa8qacaGGGcGaaiiOaiaadchacqGH9aqppaWaaiWaaeaapeGaaGym aiaacYcacaaIYaGaaiilaiabgAci8kaacYcacaWGUbaapaGaay5Eai aaw2haaaaa@434E@
  2. Step 2: For k=1,2,…,n: select the k th MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaieaaaaaa aaa8qacaWGRbWdamaaBaaajuaibaWdbiaadshacaWGObaajuaGpaqa baaaaa@3A85@  digit in factoradic representation, and find this digit in f={ 0,1,,n1 } MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaieaaaaaa aaa8qacaWGMbGaeyypa0ZdamaacmaabaWdbiaaicdacaGGSaGaaGym aiaacYcacqGHMacVcaGGSaGaamOBaiabgkHiTiaaigdaa8aacaGL7b GaayzFaaaaaa@42A2@ . Assume that this digit is the ith digit in f={ 0,1,,n1 } MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaieaaaaaa aaa8qacaWGMbGaeyypa0ZdamaacmaabaWdbiaaicdacaGGSaGaaGym aiaacYcacqGHMacVcaGGSaGaamOBaiabgkHiTiaaigdaa8aacaGL7b GaayzFaaaaaa@42A2@ . Select the i th MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaieaaaaaa aaa8qacaWGPbWdamaaBaaajuaibaWdbiaadshacaWGObaapaqabaaa aa@39F5@  element of p; set this element as the k th MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaieaaaaaa aaa8qacaWGRbWdamaaBaaajuaibaWdbiaadshacaWGObaajuaGpaqa baaaaa@3A85@  element of permutation, and omit this element from p. Table 3 demonstrates the mapping of ( 1 2 1 1 0 0 )  ( 2  3  1 ) MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfa4aaeWaae aaqaaaaaaaaaWdbiaaigdapaWaaSbaaKqbGeaapeGaaGOmaaqcfa4d aeqaa8qacaaIXaWdamaaBaaajuaibaWdbiaaigdaaKqba+aabeaape GaaGima8aadaWgaaqcfasaa8qacaaIWaaajuaGpaqabaaacaGLOaGa ayzkaaWdbiaabccacqGHsgIRcaqGGaWdamaabmaabaWdbiaaikdaca qGGaGaai4eGiaabccacaaIZaGaaeiiaiaacobicaqGGaGaaGymaaWd aiaawIcacaGLPaaaaaa@4AF7@  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 ( 1 2 1 1 0 0 ) MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfa4aaeWaae aaqaaaaaaaaaWdbiaaigdapaWaaSbaaKqbGeaapeGaaGOmaaqcfa4d aeqaa8qacaaIXaWdamaaBaaajuaibaWdbiaaigdaaKqba+aabeaape GaaGima8aadaWgaaqcfasaa8qacaaIWaaajuaGpaqabaaacaGLOaGa ayzkaaaaaa@3FCF@ MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaieaaaaaa aaa8qacqGHsgIRaaa@3891@   ( 2  3  1 ) MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfa4aaeWaae aaqaaaaaaaaaWdbiaaikdacaqGGaGaai4eGiaabccacaaIZaGaaeii aiaacobicaqGGaGaaGymaaWdaiaawIcacaGLPaaaaaa@3E6A@ based on Algorithm 2.

Proposed IWO algorithm

  1. Step 1: Set the values of the control parameters: N int MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaieaaaaaa aaa8qacaWGobWdamaaBaaajuaibaWdbiaadMgacaWGUbGaamiDaaqc fa4daeqaaaaa@3B5C@ (number of initial seed), P max MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaieaaaaaa aaa8qacaWGqbWdamaaBaaajuaibaWdbiaad2gacaWGHbGaamiEaaqc fa4daeqaaaaa@3B59@ (maximum number of plant can be survived in every iteration), ite r max MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaieaaaaaa aaa8qacaWGPbGaamiDaiaadwgacaWGYbWdamaaBaaajuaibaWdbiaa d2gacaWGHbGaamiEaaqcfa4daeqaaaaa@3E4C@   (maximum number of iterations), S max MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaieaaaaaa aaa8qacaWGtbWdamaaBaaajuaibaWdbiaad2gacaWGHbGaamiEaaqc fa4daeqaaaaa@3B5C@  (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 MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaieaaaaaa aaa8qacaWGZbGaamiza8aadaWgaaqcfasaa8qacaWGPbGaamOBaiaa dMgacaWG0bGaamyAaiaadggacaWGSbaajuaGpaqabaaaaa@401D@  (initial value of standard deviation), and s d final MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaieaaaaaa aaa8qacaWGZbGaamiza8aadaWgaaqcfasaa8qacaWGMbGaamyAaiaa d6gacaWGHbGaamiBaaqcfa4daeqaaaaa@3E33@  (final value of standard deviation).
  2. 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.
  3. 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.
  4. 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 S min MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaieaaaaaa aaa8qacaqGtbWdamaaBaaajuaibaWdbiaab2gacaqGPbGaaeOBaaqc fa4daeqaaaaa@3B52@ and S max MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaieaaaaaa aaa8qacaqGtbWdamaaBaaajuaibaWdbiaab2gacaqGHbGaaeiEaaqc fa4daeqaaaaa@3B54@ .
  5. 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.
  6. Step 6: Compute the fitness values of the new plants.
  7. 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.

  1. 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 n-1.

In this proposed IWO algorithm, the described procedures is applied to q% of the population in every iteration randomly.

  1. 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 [ dminλ, dmin+λ ], MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfa4aamWaae aaqaaaaaaaaaWdbiaadsgacaWGTbGaamyAaiaad6gacqGHsislcqaH 7oaBcaGGSaGaaeiiaiaadsgacaWGTbGaamyAaiaad6gacqGHRaWkcq aH7oaBa8aacaGLBbGaayzxaaWdbiaacYcaaaa@4767@ where dmin=P(1TEF), P=( i=1 n p i )+( n 2 × i=1 n b i MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaieaaaaaa aaa8qacaWGKbGaamyBaiaadMgacaWGUbGaeyypa0JaamiuaiaacIca caaIXaGaeyOeI0IaamivaiaadweacaWGgbGaaiykaiaacYcacaGGGc Gaaeiuaiabg2da9maabmaapaqaa8qadaGfWbqabKqbG8aabaWdbiaa bMgacqGH9aqpcaaIXaaapaqaa8qacaqGUbaajuaGpaqaa8qacqGHri s5aaGaaeiCa8aadaWgaaqcfasaa8qacaqGPbaajuaGpaqabaaapeGa ayjkaiaawMcaaiabgUcaRiaacIcadaWcaaWdaeaapeGaaeOBaaWdae aapeGaaGOmaaaacqGHxdaTdaGfWbqabKqbG8aabaWdbiaabMgacqGH 9aqpcaaIXaaapaqaa8qacaqGUbaajuaGpaqaa8qacqGHris5aaGaae Oya8aadaWgaaqcfasaa8qacaqGPbaajuaGpaqabaaaaa@6047@  and λ=P( RDD/2 ) MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaieaaaaaa aaa8qacqaH7oaBcqGH9aqpcaWGqbWdamaabmaabaWdbiaadkfacaWG ebGaamiraiaac+cacaaIYaaapaGaayjkaiaawMcaaaaa@3FC2@ .

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:

Nint=n, Pmax=n, itermax=5×n, Smax=3, Smin=1, n=2, sdinitial= n 2 ,  sdfinal =2, k=10% MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaieaaaaaa aaa8qacaqGobGaaeyAaiaab6gacaqG0bGaeyypa0JaaeOBaiaacYca caGGGcGaaeiuaiaab2gacaqGHbGaaeiEaiabg2da9iaab6gacaGGSa GaaiiOaiaabMgacaqG0bGaaeyzaiaabkhacaqGTbGaaeyyaiaabIha cqGH9aqpcaaI1aGaey41aqRaaeOBaiaacYcacaGGGcGaae4uaiaab2 gacaqGHbGaaeiEaiabg2da9iaaiodacaGGSaGaaiiOaiaabofacaqG TbGaaeyAaiaab6gacqGH9aqpcaaIXaGaaiilaiaacckacaqGUbGaey ypa0JaaGOmaiaacYcacaGGGcGaae4CaiaabsgacaqGPbGaaeOBaiaa bMgacaqG0bGaaeyAaiaabggacaqGSbGaeyypa0JaaeOBa8aadaahaa qabKqbGeaapeGaaGOmaaaajuaGpaGaaiila8qacaGGGcGaaiiOaiaa bohacaqGKbGaaeOzaiaabMgacaqGUbGaaeyyaiaabYgacaqGGcGaey ypa0JaaGOmaiaacYcacaGGGcGaam4Aaiabg2da9iaaigdacaaIWaGa aiyjaaaa@8412@  and q=5% MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaieaaaaaa aaa8qacaWGXbGaeyypa0JaaGynaiaacwcaaaa@3A08@ . 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:

PRD= alg sol min sol min sol   MathType@MTEF@5@5@+= feaagKart1ev2aqatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaieaaaaaa aaa8qacaqGqbGaaeOuaiaabseacqGH9aqpdaWcaaWdaeaapeGaaeyy aiaabYgacaqGNbWdamaaBaaajuaibaWdbiaabohacaqGVbGaaeiBaa qcfa4daeqaa8qacqGHsislcaqGTbGaaeyAaiaab6gapaWaaSbaaKqb GeaapeGaae4Caiaab+gacaqGSbaajuaGpaqabaaabaWdbiaab2gaca qGPbGaaeOBa8aadaWgaaqcfasaa8qacaqGZbGaae4BaiaabYgaaKqb a+aabeaaaaWdbiaabckaaaa@5086@  (5)

Where Alg sol   MathType@MTEF@5@5@+= feaagKart1ev2aqatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaieaaaaaa aaa8qacaqGbbGaaeiBaiaabEgapaWaaSbaaKqbGeaapeGaae4Caiaa b+gacaqGSbaajuaGpaqabaWdbiaabckaaaa@3E57@ 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 near-optimum 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 NP-hard 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 near-optimal 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 sub-algorithm 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

  1. Pinedo M (1995) Scheduling: Theory, Algorithms and Systems. Springer.
  2. 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): 404-413.
  3. Liao CJ, Choi JY (1995) A genetic algorithm for job sequencing problems with distinct due dates and general early-tardy penalty weights. Computers and Operations Research 22(8): 857-869.
  4. 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): 29-38.
  5. 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): 166-175.
  6. Kaweegitbundit P (2011) A Single Machine Scheduling Problem with Earliness and Tardiness Penalties Using Memetic Algorithm. Advanced Materials Research 314: 2353-2357.
  7. Kedad-Sidhoum S, Sourd F (2010) Fast neighborhood search for the single machine earliness-tardiness scheduling problem. Computers and Operations Research 37(8): 1464-1471.
  8. Allaoua H, Osmane I (2010) Variable parameters lengths genetic algorithm for minimizing earliness-tardiness penalties of single machine scheduling with a common due date. Electronic Notes in Discrete Mathematics 36(C): 471-478.
  9. Fan J, Xu D (2010) Some single-machine scheduling problems with aging effect. IEEE Explore.
  10. Janiak A, Rudek R (2010) Scheduling jobs under an aging effect. Journal of the Operational Research Society 61(6): 1041-1048.
  11. Ji M, Hsu CJ, Yang DL (2011) Single-machine scheduling with deteriorating jobs and aging effects under an optional maintenance activity consideration. Journal of Combinatorial Optimization 26(3): 437-447.
  12. Rudek R (2012) Some single-machine scheduling problems with the extended sum-of-processing-time-based aging effect. International Journal of Advanced Manufacturing Technology 59(1-4): 299-309.
  13. Rudek R (2012) The strong NP-hardness of the maximum lateness minimization scheduling problem with the processing-time based aging effect. Applied Mathematics and Computation 218(11): 6498-6510.
  14. Yang SJ, Yang DL (2010) Minimizing the makespan on single-machine scheduling with aging effect and variable maintenance activities. Omega 38(6): 528-533.
  15. Mehrabian AR Lucas C (2006) A novel numerical optimization algorithm inspired from weed colonization. Ecological Informatics 1(4): 355-366.
  16. Knuth DE (1973) Semi-numerical algorithms. (3rd edn), The Art of Computer Programming, Addison-Wesley Longman Publishing Co Boston, MA, USA.
  17. McCaffrey J (2003) Using permutations. NET for improved systems security.
  18. Behroozi M (2009) A meta-heuristic approach for a special class of job shop scheduling problem. Faculty of industrial engineering. Tehran, Sharif University of Technology, Iran.
© 2014-2016 MedCrave Group, All rights reserved. No part of this content may be reproduced or transmitted in any form or by any means as per the standard guidelines of fair use.
Creative Commons License Open Access by MedCrave Group is licensed under a Creative Commons Attribution 4.0 International License.
Based on a work at http://medcraveonline.com
Best viewed in Mozilla Firefox | Google Chrome | Above IE 7.0 version | Opera |Privacy Policy