Andreas C Nearchou
email: nearchou@upatras.gr

Scheduling with controllable processing times and compression costs using population-based heuristics

Keywords: SCHEDULING, EVOLUTIONARY ALGORITHMS controllable processing times, crash costs scheduling, controllable processing times, crash costs, meta-heuristics, differential evolution, swarm intelligence, genetic and evolutionary algorithms, evolution strategies

Scheduling with controllable processing times and compression costs using population-based heuristics

Andreas C.

Introduction

Scheduling involving controllable job processing times has received increasing research attention in the last two decades due to its compliance with the real needs of modern production systems. In such systems, production managers usually face the problem of scheduling the jobs at faster processing times with higher costs. Jobs' processing times are usually controllable (compressible) by allocating additional resources, such as working overtime, performing subcontracting, running machines at higher speeds, consuming more energy, fuels, etc. The efficient coordination of job scheduling and resource allocation decisions is a critical factor for a modern production system to achieve competitive advantage.

This paper considers the problem of scheduling multiple jobs with controllable processing times on a single machine and the objective to minimize the total weighted job completion time plus the cost of compression. We will refer to this problem as TWJCTP for short.

TWJCTP is NP-hard (Wan et al. 2001, Hoogeveen and[START_REF] Hoogeveen | Some comments on sequencing with controllable processing times[END_REF] and consequently the right way to proceed is through the use of heuristic techniques. In all our knowledge no other heuristic exists in the literature for directly solving large size instances of TWJCTP.

This paper aims at contributing to fill this gap facing TWJCTP by means of modern population-based heuristics namely differential evolution (DE), particle swarm optimization (PSO), genetic algorithm (GA), and evolution strategies (ES). The performance of each one of them is examined under the influence of two different encoding schemes necessary for mapping the genotypes (evolving vectors) to phenotypes (actual job schedules). A new, simple control scheme for estimating the control parameters settings for the case of DE, PSO and GA is also presented. The proposed control scheme is adaptive and found superior to traditional deterministic control schemes with regard to the quality of solutions obtained.

The scheduling problem with controllable processing times and costs has been studied by researchers such as (Vickson 1980a, 1980b[START_REF] Van Wassenhove | A bicriterion approach to time/cost trade-offs in sequence[END_REF][START_REF] Daniels | Single machine scheduling with controllable processing times and number of jobs tardy[END_REF][START_REF] Zdrzalka | Scheduling jobs on a single machine with release dates, delivery times and controllable processing times: worst-case analysis[END_REF][START_REF] Panwalkar | Single-machine sequencing with controllable processing times[END_REF][START_REF] Alidace | Two parallel machine sequencing problems involving controllable job processing times[END_REF][START_REF] Guochun | Single machine scheduling with controllable processing times and compression costs (Part I: equal times and costs)[END_REF][START_REF] Biskup | Single machine scheduling with controllable processing times and earliness, tardiness and completion time penalties[END_REF][START_REF] Foulds | Single machine scheduling with controllable processing times and compression costs (Part II: Heuristics for the general case)[END_REF][START_REF] Yen | Single machine scheduling to minimize total compression plus weighted flow cost is NP-hard[END_REF][START_REF] Hoogeveen | Some comments on sequencing with controllable processing times[END_REF]. Vickson (1980aVickson ( , 1980b) ) initiates the topic, first, by considering the problem with the objective of minimizing the total flow time and the total processing cost incurred due to the job processing time compression (Vickson 1980a). Then by considering the problem of minimizing the total flow and resource costs under the assumption that the job flow costs are identical (Vickson 1980b). [START_REF] Van Wassenhove | A bicriterion approach to time/cost trade-offs in sequence[END_REF] proposed an algorithm to determine the trade-off curve between maximum tardiness and total amount of compression on a single machine. Later, [START_REF] Daniels | Single machine scheduling with controllable processing times and number of jobs tardy[END_REF] extended the work of [START_REF] Van Wassenhove | A bicriterion approach to time/cost trade-offs in sequence[END_REF] by considering the additional constraint of allowed maximum job tardiness. [START_REF] Zdrzalka | Scheduling jobs on a single machine with release dates, delivery times and controllable processing times: worst-case analysis[END_REF] scheduling problem in which each job has a release date, a delivery time and a controllable processing time; and gave an approximation algorithm for minimizing the overall schedule cost. [START_REF] Panwalkar | Single-machine sequencing with controllable processing times[END_REF] considered the common due date assignment and single machine scheduling problem in which the objective is the sum of penalties based on earliness, tardiness and processing time compressions. The authors showed that the problem can be reduced to a linear assignment problem. Their results extended later by [START_REF] Alidace | Two parallel machine sequencing problems involving controllable job processing times[END_REF] to the parallel machine scheduling case. [START_REF] Biskup | Single machine scheduling with controllable processing times and earliness, tardiness and completion time penalties[END_REF] also extended the work of [START_REF] Panwalkar | Single-machine sequencing with controllable processing times[END_REF] by adding the total completion time in the objective function, and showed that the extended problem can be solved as an assignment problem. An early survey with results on the specific research field can be found in [START_REF] Nowicki | A survey of results for sequencing problems with controllable processing times[END_REF]). An up-to-date extended survey in the field together with a unified framework for the related scheduling problems can be found in the recent paper of [START_REF] Shabtay | A survey of scheduling with controllable processing times[END_REF].

The rest of this paper is organized as follows: Section 2 formulates TWJCTP. Section 3 describes very briefly DE, PSO, GA and ES. Section 4 introduces the way the four population-based heuristics can be applied on TWJCTP, while Section 5 presents and discusses the results of the experimental evaluations of the algorithms. Finally, Section 6 summarizes the contribution of the paper and states some directions for future work.

Problem formulation

To facilitate the presentation, the following notations are used throughout the paper:

∑ ∑ = = + = + = n i i i n i i i CoC TWCT y C w f f f 1 ] [ ] [ 1 ] [ ] [ ) , ( π π π π φ π y (1) The completion time of ] [i π is estimated by ( ) ∑ = = - i j j j i y np C 1 ] [ ] [ ] [ π π π (2)
Hence, ƒ is a bi-criteria objective function composed by total weighted completion time of the n jobs in π , and the corresponding total cost of compressing these jobs. According to the literature [START_REF] Hoogeveen | Multicriteria Scheduling[END_REF]Woeginger 2002, Hoogeveen 2005), four variants of the basic TWJCTP arise: P1: to minimize the total cost given by Eq.( 1), P2: to minimize i.e., the set of solutions that are not dominated by any other solution in the search space when all the objectives are considered, and they do not dominate each other in the set.

∑ = = n i i i TWCT C w f 1 ] [ ] [ π π under the constraint A y f n i i i CoC ≤ = ∑ =1 ] [ ] [ π π
Lemma 1: There is always an optimal schedule to TWJCTP in which every job i J (i=1,…,n) is either totally uncompressed ( i y =0), or totally compressed ( i y = i u ). The proof can be found in [START_REF] Hoogeveen | Some comments on sequencing with controllable processing times[END_REF].

Population-based heuristics

DE [START_REF] Storn | Differential Evolution -A simple and efficient heuristic for global optimization over continues spaces[END_REF], PSO [START_REF] Eberhart | A new optimizer using particle swarm theory[END_REF], GAs [START_REF] Holland | Adaptation in natural and artificial systems: an introductory analysis with application to biology, control and artificial intelligence[END_REF] and ES (introduced in the early of 1960s by Rechemberg and Schwefel; see [START_REF] Fogel | Evolutionary Computation[END_REF] for a detailed description) belong to a modern class of heuristics known as evolutionary algorithms.

Independently of the form of the optimization problem, any evolutionary algorithm undergoes the following general operation mechanism [START_REF] Michalewicz | How to solve it: Modern heuristics[END_REF]: [1,n]). To that purpose, a real-valued vector containing 2n real numbers has been made was selected for use (see Fig. 1). The n most left components of the vector corresponds to π and its n most right components corresponds to y . In the following we will refer to the two parts of the vector with π-part and y-part for short, respectively.

y π ∈[0, ] [i u π ] ∀ i∈

< Insert Figure 1 about here >

Creating a job sequence from a real-valued vector

After the decision about the structure of the implemented genotype, a way to map this structure to an actual TWJCTP solution must be determined. In the literature there are at least two different encoding schemes for representing permutations through real-valued vectors namely, random keys [START_REF] Bean | Genetics and random keys for sequencing and optimization[END_REF]) and sub-range keys [START_REF] Nearchou | Meta-heuristics from nature for the loop layout design problem[END_REF]. Both of them were adopted and their influence on the performance of the examined heuristics was investigated.

The application of the two encoding schemes on TWJCTP is explained below through a simple example. (3)

< Insert

Random keys work as follows: the numbers in π-part of x are sorted and their order in x determines π . That is, (0.75, 0.42, 0.10, 0.27, 0.62) corresponds to the job sequence (3-4-2-5-1). Since the 3 rd number in the vector has the lowest value (=0.10), followed by the 4 th number in the vector, which is the second smallest number (=0.27), etc.

Sub-range keys work as in the following: the range [1…n] is divided into n equal subranges and the upper bound of each sub-range is saved in an array SR=[1/n, 2/n, …,n/n] T (SR stands for Sub-Ranges). Then, we take each number from π-part and determine the sub-range in which this number belongs. The order of these sub-ranges in SR constitutes the final solution. For the above example, n=5 and thus,

T SR ] 1.0 0.8, 0.6, 0.4, 0.2, [ = .
The first number from π-part (=0.75) lies in the fourth sub-range (0.6<0.75≤0.8), therefore the resulting schedule is (4 _ _ _ _ ). The second number (=0.42) lies in the third sub-range (0.4<0.42≤0.6), and so on. Finally, the generated (by sub-range keys) schedule is (4 3 1 2 4).

As it is clear, this schedule is illegal since it contains duplicated jobs. To produce a valid version of the schedule the following very simple two-steps repairing procedure is applied on the proto-schedule:

(a) Delete all the duplicate jobs: (4 3 1 2 _) (b) Fill the empty locations in the schedule with the remaining (unused) jobs following an ascending order of their values: (4 3 1 2 5)

Therefore, (0.75, 0.42, 0.10, 0.27, 0.62) corresponds to the job sequence (4-3-1-2-5), which is different from that obtained by random-keys.

Creating a compression vector from a real-valued vector

It is now the time to obtain the compression vector y corresponding to x . To achieve this mapping, the following encoding mechanism is proposed x is the corresponding real number in y-part of x . If j

   - ≤ = otherwise , 5 . 0 if , 0 ] [ n j j j u x y π for all j=n+1,n+2,…,2n (4)
x is less than or equal to 0.5 then

job ] [ n j - π
is not compressed at all, or is totally compressed. Note that, Eq. ( 4) implements lemma 1 for optimal TWJCTP solution.

Therefore, applying Eq. (4) on the above example (Eq. ( 3)), results in a mapping of y-part into vector y =(0,0,8,0,4) if random-keys method is adopted; and y =(0,0,4,0,7) if sub-range keys method is adopted. The total cost for the two TWJCTP solutions (π ; y ) random- keys =(3,4,2,5,1;0,0,8,0,4) and (π ; y ) sub-range-keys =(4,3,1,2,5;0,0,4,0,7), are thereby 1415 and 1664 units, respectively.

A multi-objective procedure for TWJCTP

The attempt with the multi-objective problem (MOP) studied in this paper is to find a Pareto set of optimal solutions for ( TWCT f , CoC f ) (see Eq.( 1)). A Pareto set contains all those not dominated solutions to TWJCTP, such that no other solutions are superior to them in respect to both the objectives shown in Eq.( 1). In order to determine a Pareto set of TWJCTP solutions, the operation mechanism of each one of the four heuristics under consideration was enhanced with the following two main features: a)

A separate secondary population of diverse Pareto-optimal TWJCTP solutions is maintained and iteratively updated from generation to generation. This population will be composed of all Pareto solutions found during the search.

b)

The main population is iteratively updated using an elitist preserving strategy. Based on this strategy, a portion of the main population is randomly replaced by a number of elite Pareto solutions.

In MOP a solution with the best values for each objective can be regarded as an elite solution. Hence, for TWJCTP there are two elite (extreme) solutions in the evolving population each of which optimizes one objective. These solutions are candidates to be copied into Pareto population. Pareto set is further completed by additional elite solutions using the procedure given below. A Pareto population of the final generation contains the near-optimal solutions to TWJCTP. The decision maker can then select that solution accomplishing more her or his preferences. Replace two randomly selected members in S with the two elite Pareto;

Return (S, Γ); End;

Fitness assignment mechanism

A critical question arising when facing a MOP by the means of evolutionary algorithms is how to estimate the fitness function of individual solutions with regard to the multiple objectives. A simple method to combine multiple objective functions into a composite fitness solution is the well-known weighted-sum method. According to this method, the MOP under consideration is written as in the following: The weights 1 ω and 2 ω specify the relative importance of the corresponding objectives.

∑ ∑ = = ⋅ + ⋅ = ⋅ + ⋅ = n i i i n i i i CoC TWCT y C w f f f 1 ] [ ] [ 2 1 ] [ ] [ 1 2 1 ) , ( min π π π π φ ω ω ω ω π y (5)
The determination of the suitable values for these weights is in general a difficult task and constitutes another critical research issue in multi-objective optimization. In the literature, there are three general methods to compute the weights i ω (i=1,…,Q) for a weighted-sum objective function with Q objectives: the fixed-weight method, the random-weight method and the adaptive-weight method. The former uses constant weights satisfying the relation,

,Q , i f i i Q i K 1 all or 0 , 1 1 = > ∑ = = ω ω (6)
However, as [START_REF] Murata | Multi-objective genetic algorithms and its application to flowshop scheduling[END_REF] showed, using constant weights within an evolutionary algorithm the search direction is fixed, and for this reason it is difficult for the search process to obtain a variety of not dominated solutions. To overcome this drawback, [START_REF] Murata | Multi-objective genetic algorithms and its application to flowshop scheduling[END_REF], proposed the use of random weights according to the following formula,

,Q , i Q random random i random i K L , 2 1 2 1 random = + + + = ω (7)
where i random (i=1,…,Q) are non-negative random numbers.

Furthermore, [START_REF] Cheng | Genetic Algorithms and Engineering Optimisation[END_REF] proposed an adaptive-weight method which readjusts the weights by utilizing some useful information from the current population. This method computes the weights by,

,Q , i f i z i z i K 1 all or , min max 1 = - = ω (8)
where max i z and min i z are the maximum and minimum values of the i th objective in the population, respectively.

After much experimentation with the above methods we found the random-weight method superior to the others with regard to the quality of the solutions obtained, and hence it was decided to adopt this method in our study. The performance of the heuristics was quantified through the use of the following indices: (c) The quality ratio P*/P in percentage. The larger the value for this ratio for a given heuristic, the higher the performance of the heuristic.

F

(d) The actual processing time consumed in seconds.

To get the average performance of the heuristics, each one of them was run 20 times over every test instance (starting each time from a different random number seed) and the solution quality was averaged. Hence, as there are 10 instances in each one of the 6 categories of problems, this means that each heuristic was run 6×10×20 times=1200 times in total. All the

Choice of the control parameters

When designing a population-based heuristic among others, one has to decide about the size Ns of the population used. This is a common parameter for all the examined heuristics.

To make the heuristics comparable it was decided to use the same Ns=n population size for all, and limit the running process of each one of them to a maximum of 3n CPU seconds. This means a maximum running time for them equal to 15 sec for 5-job problems, 30 sec for 10-job problems, etc. The size of the Pareto population was defined to be equal to 50 for the small size instances (n≤20) and equal to 100 for the large size instances (n≥50). It is worth pointing out that the basic data structures required are identical for all compared algorithms.

The settings for the additional control parameters involved in DE, PSO and rGA were determined after experimenting with two different control schemes: a static scheme consistent to the general indications of the literature, and a proposed dynamic control scheme with which some parameters are fixed during the search process while some other parameters are altered according to the diversity of the entire population. These control schemes are described below in detail, while a synopsis of them is given in Table 2.

< Insert Table 2 about here >

a) DE -static control scheme: Crossover rate (C R ) was defined to take values within the discrete range {0.01, 0.1, 0.5, 0.7, 0.9} while varying F (a scaling positive parameter used in the creation of the mutant vectors) to take a value within the range {0.5, 0.75, 0.95}. That is, this scheme results in 15 different combinations of (C R , F).

DE -dynamic control scheme: C R was set equal to 0.01 and F being adapted within the range [0.4, 1.0] as in the following. At the beginning of the search process, F is high (F=F 0 =1) and decreases slowly by a factor ϑ=0.9 using the relation F=ϑ×F. When the population's diversity becomes too 'small', or F becomes lower than 0.4, then it takes again its initial high value (F=F 0 ). A small diversity of the population is encountered when the fitness of the worst member of the population (fitness worst ) and the average population fitness (fitness avg ) are almost the same. That is, F is being estimated by the following rule:

F F else F F then ) (F ) or fitness . s if (fitnes avg worst × = = < × ≥ ϑ 4 . 0 95 0 0 (9)
It is also highlighted that mutant vectors in DE were implemented using the standard DE1 scheme [START_REF] Storn | Differential Evolution -A simple and efficient heuristic for global optimization over continues spaces[END_REF]. b) PSO -static control scheme: We followed the indications of [START_REF] Kennedy | The behavior of particles[END_REF], [START_REF] Parsopoulos | Recent approaches to global optimization problems through particle swarm optimization[END_REF]. Firstly, c 1 and c 2 (cognitive and social parameters) were both set to a fixed and equal value within the range {0.5, 1.0, 2.0}. Then, since some recent works [START_REF] Parsopoulos | Recent approaches to global optimization problems through particle swarm optimization[END_REF] report that it might be better to choose c 1 >c 2 , with c 1 +c 2 ≤4, experiments were also performed using the combination c 1 =2, c 2 =1.5. The experimental investigations led us to adopt the latter settings since higher quality solutions were encountered. Furthermore, inertia weight factor Iw was defined to gradually decreased from Iw 0 =1.2 towards 0.4 using the relation Iw=Θ×Iw (with Θ=0.95). If Iw becomes lower than 0.4 then it is reset to Iw 0 . PSO -dynamic control scheme: c 1 and c 2 are estimated as in the static scheme. Iw by the relation Iw=Θ×Iw, starting from Iw 0 and being reset to this value if the following condition exists: (Iw<0.4) or (fitness worst ≥0.95×fitness avg ). c) rGA, -static control scheme: We experimented with various recommended crossover and mutation rates [START_REF] Goldberg | Genetic algorithms in search, optimization, and machine learning[END_REF]) such as C R ∈{0.6, 0.8} and M R ∈{0.01, 0.0333, 1/n, 0.1}. rGA, -dynamic control scheme: A fixed crossover rate equal to 1.0 was defined, and an adapted mutation rate M R ∈[0.1, 0.8] which is high at the beginning and decreases slowly by the population's diversity. When the population's diversity becomes too 'small', then M R takes again its original high value. More specifically, M R is initially defined equal to 0.8, and decreased in each new generation by a factor ϑ=0.9 using the relation M R =ϑ×M R . Similarly, to DE and PSO, a small population's diversity is encountered when the minimum population fitness and the average population fitness are almost the same. M R is reset to 0.8 if the following condition is satisfied: (M R <0.0333) or (fitness worst ≥0.95×fitness avg ). The three genetic operators, i.e., selection, crossover, and mutation were implemented through binary tournament selection, one-point crossover and uniform mutation, respectively. These operators were found to be the best among a set of known operators with regard to the quality of the solutions obtained.

After much experimentation with the above schemes the following best settings for the control parameters were determined: for DE, the dynamic scheme i.e., (C R , F)=(0.01, adapted within the range [0.4, 1.0] using Eq.( 9)). For PSO, the static scheme (c 1 , c 2 , k Iw )=(2, 1.5, adapted within the range [0.4, 1.2]). For rGA, the static scheme with (C R ,M R )=(0.8, 0.01). All the results presented below are conducted by these settings.

d) For the case of ES, we followed the recommendations of the literature [START_REF] Eiben | Introduction to evolutionary computing[END_REF]. After experimentation for choosing the correct survivor selection scheme, we found that using (µ,λ)-scheme within ES results in a much superior optimizer to that of using (µ+λ)scheme. For this reason (µ,λ)-scheme was adopted. µ was estimated using the heuristic rule λ/µ=7. Mutation was performed through Gaussian perturbation. The mutation step sizes σ were estimated using self-adaptation through a suitable formation of the genotype structure.

In particular, for n-job TWJCTP, the genotype in ES has the form } , , ; , , {

1 1 n n x x σ σ K K .x
part of the genotype denotes the real-valued vector solution and σ part of the genotype the mutation step size corresponding to each component of the real-valued vector. Offspring were generated using discrete recombination for x values and intermediate recombination for σ values.

Comparative results

For each one of the examined heuristics two versions were implemented corresponding to a distinct encoding scheme, either to random-keys, or to sub-range keys. In the following we will refer to them by the abbreviations xx1 (meaning heuristic xx with random-keys) and xx2

(heuristic xx with sub-range keys) for short. Depending on the problem size the following (see Table 3) average processing times were needed. These times correspond to the mean CPU time spent by each heuristic till the creation of the best individual solution within the permitted running duration. As can be seen from Table 3, DE heuristics seem to be the fastest optimizers especially for large size problems. Almost identical average convergence times are reported for all the heuristics on the small size problems. While rGA and ES appear to have the slowest rate of convergence for problems with size greater than 50.

< Insert Table 3 about here >

Table 4 displays the number of unique Pareto solutions obtained by each one of the heuristics after a single trial over the 60 test beds. For example, for 5-job problems (n=5) in the case of the first test instance, three of the heuristics (de1, rga1, es2) determined 13 different Pareto solutions, while each one of the rest five heuristics determined 14 Pareto solutions. For 10-and 20-job problems, PSO heuristics (pso1, pso2) managed to obtain a larger set of Pareto solutions than that obtained by the other heuristics. For 50-job problems de1 and pso2 outperformed all the others with the latter being slightly better. While, in the case of the most difficult classes of problems (n=100, 200) DE heuristics (de1, de2) showed the highest performance, generating a larger set of Pareto solutions than that obtained by the other approaches. ∇) and those obtained by de2 (○) are of higher quality (lower curves) than those obtained by the other approaches. Similar high performance for pso1, pso2 and de2 can be also observed for the large size instances. In the most difficult class of problems (n=200) de2 and pso2 clearly outperforms all the other approaches. Poor performance was encountered in the case of de1 and rga1 heuristics (higher curves in Fig. 2). Some solutions obtained by them have small values of TWCT and others have small values of CoC, while very few solutions have small values of both objectives if compared with the not dominated solutions obtained by the other heuristics. The performance of ES approaches is higher than that of de1 and rga1, but inferior than that of pso1, pso2 and de2.

< Insert

< Insert Figure 2 about here >

The above discussion concerns the results obtained by the heuristics after a single trial over each one of the 60 test instances. Due to the stochastic behavior of these heuristics, one must evaluate their average performance after multiple trials on the test beds. Hence, each heuristic was applied 20 times on each one of the 60 test instances. After each trial, we first reported the unique Pareto solutions (index P) obtained by each heuristic. Then, all the obtained solutions were compared to each other, and the not dominated among them were selected (index P*). The values of P and P* were averaged over the 20 trials of each heuristic on every test instance. Recall that, every new trial was starting from a different random number seed (same for all the examined heuristics). Tables 5 and6 display the final averaged values of P and P* respectively, on the examined test instances. To make things more clearly, we describe some lines of these tables. For example, let us take the case of the 1 st instance of 100-job problems (n=100) and measure P (Table 5). As one can see, best results for this instance were obtained by de1 (P=25.4) and worst results by es2 (P=14.6). That is, de1 was found able to generate a Pareto set of 25.4 unique solutions in average, while the corresponding ability of es2 was a Pareto set of 14.6 solutions in average. But how good were the obtained solutions? The answer to this question can be found in Table 6. In particular, for the specific benchmark (n=100, 1 st instance), only 0.2 solutions in average from the Pareto set obtained by de1 (P*=0.2) were not dominated by any other solution. This is the smallest P* value among the examined heuristics for the specific test instance. Meaning that, although the variety of the solutions obtained by de1 was in average greater than that of the other approaches (P=25.4, from 5 and6. Particularly, Table 7 displays the mean values of P and P* (Table 7(a)) and quality ratio (P*/P) (Table 7(b))

averaged over the 10 instances of each different benchmark class. As can be seen from Table 7(b), best results are due to de2 which achieved a % quality ratio equal to 98.5, 85.5 and 43.1 for small size problems (n=5, 10 and 20), respectively; and a quality ratio equal to 65.7% for 50-job problems, 71% for 100-job, and approximately 75.5% for 200-job problems.

The second best performance was achieved by PSO heuristics with pso2 being slightly better than pso1 for large size instances (n=100, 200). The worst performance was due to de1 and es1. Furthermore, examining the influence of the two encoding schemes (random-keys and sub-range keys) on the performance of the examined heuristics, one can safely conclude that sub-range keys are more suitable to be used within DE. For the other three approaches both coding schemes seem to perform almost the same, with random-keys being slightly more suitable within PSO and sub-range keys being more suitable within rGA and ES.

< Insert Table 7 about here >

Finally, to verify the correctness of the reported results it was decided to test the performance of the heuristics over a similar scheduling problem for which polynomial time exact algorithms exists. The additional experiments were performed on problem 1/contr/∑C i .

The objective of this problem is to minimize the total job completion time plus the total cost incurred due to job processing time compression. As Vickson (1980a) showed, assuming equal weight factors ( n w = ) for all the n jobs, this scheduling problem can be formulated as an assignment problem and solved to optimality by an assignment algorithm such as the famous Kuhn's Hungarian algorithm [START_REF] Bazaraa | Linear Programming and Network Flows[END_REF]. As test beds we select the test instances with n=5 and n=10 included in the benchmarks data set described above. Table 8 reports the optimum solutions obtained by Vickson's method for these instances. All of the examined heuristics found rather easily the particular optimum solutions so it was decided to 9. Note that, the first four jobs in the generated optimum schedule (i.e. jobs 3, 6, 10, 1) are crashed while the other jobs are not crashed.

< Insert

Conclusions

Scheduling jobs with controllable processing times on a single machine and objective to minimize the total weighted job completion time plus the cost of compression is an NP-hard bi-criteria combinatorial optimization problem. Therefore, large size instances of the problem must be tackled through the use of heuristics. This paper examined the performance of four known population-based heuristics, namely, differential evolution (DE), particle-swarm optimization (PSO), genetic algorithm (GA), and evolution strategies (ES), for the solution of this problem. An appropriate problem representation was developed and two different encoding schemes for mapping the genotypes (evolving vectors) to phenotypes (actual job schedules) were investigated, namely random-keys and sub-range keys, respectively. Furthermore, a new technique for dynamically estimating the correct settings of the heuristics' control parameters was presented and examined to improve their efficiency.

Extensive experiments were performed over a set of randomly generated test problems with up to 200 jobs. The results obtained showed that DE with sub-range keys is by far superior to the other approaches with regard to the quality of the solutions obtained; and rather faster with regard to the speed of convergence to near-optimal solutions. On going research considers the common due date single machine scheduling problem of a number of jobs with controllable processing times. This type of scheduling sets costs depending on whether a job finished before (earliness), or after (tardiness) the specified due date. The objective is thereby, to find a sequence of jobs that minimizes a cost function that includes the cost of earliness and tardiness, due date assignment, makespan, and resource consumption. Moreover, future work will be directed to apply similar heuristic algorithms to multi-machine scheduling problems with controllable parameters including the job processing times, release dates, and delivery times. 9. Table 1. Jobs' characteristics for a 5-job TWJCTP. 5 and6. The values are averaged over the 10 instances of each problem's category. Numbers in brackets correspond to index P * , while those outside the brackets to index P. (b) Quality ratio P*/P.

List of Tables

Static

C R ∈{0.01, 0.1, 0.5, 0.7, 0.9} F∈{0.5, 0.75, 0.95}

• c 1 =c 2 ∈{0.5, 1.0, 2.0} • c 1 =2, c 2 =1.2 Iw =Θ×Iw ∈[0.4, 1.2] C R ∈{0.6, 0.8} M R ∈{0.01, 0.0333, 1/n, 0.1} Dynamic C R =0.01
F=ϑ×F ∈[0.4, 1.0] Adapted using Eq. ( 9) 5 12.6 (11.6) 13.1 (12.5) 14.0 (13.5) 14.0 (13.4) 14.0 (13.2) 13.9 (13.3) 14.5 (13.7) 13.6 (12.9) 10 16.6 (2.2) 21.0 (17.9) 23.6 (14.4) 23.7 (16.9) 18.2 (3.0) 18.3 (4.7) 20.3 (3.9) 22.6 (6.9) 20 16.9 (0.0) 18.9 (8.1) 20.1 (8.9) 20.5 (5.2) 18.8 (1.1) 15.7 (3.3) 16.5 (0.9) 16.4 (0.8) 50 24.0 (0.0) 22.7 (14.9) 20.8 (6.5) 23.2 (4.9) 19.

c 1 =2, c 2 =1.2 Iw =Θ×Iw ∈[0.4, 1.2] adapted by population diversity C R =1.0 M R =ϑ×M R ∈[0.

  This paper studies problem P4. The trade-off curve connects all points ( consists in identifying the set of Pareto-optimal solutions for (

  (a) Create (usually in a random way) a population S of individuals that represent potential solutions to the physical problem. (b) Evaluate the quality of each individual in S. (c) Reward individuals of higher quality (so that to survive and reproduce their structure in the next generation) by introducing selective pressure on S. (d) Generate new individuals by applying variation operators on S. (e) Repeat steps (b)-(d) several times until the satisfaction of a suitable termination criterion. The main differences between DE, PSO, GAs, and ES rely on the way they perform steps (c) and (d). In particular, DE attempts to replace in each generation all the individuals in S by new, better solutions. Each individual solution becomes a target for replacement by a competitor called trial solution.

  , n+2,…,2n) denotes the amount of compression for the job lying in the (jpermitted amount of compression for this job, and j

  a) The main population of solutions S and its size Ns; (b) The Pareto population Γ and its size Γ_size. Output: The updated versions of S and Γ. Begin // Check each one of the individual solutions in S whether constitutes a Pareto solution // cS=cΓ=0 ; // initialize counters for the members in S and Γ, respectively // While (cΓ ≤ Γ_size) and (cS ≤ Ns) do cS=cS+1; Compare S(cS) with all Pareto solutions in Γ; // S(cS) is the cS th member of S // If S(cS) is not contained in Γ then If S(cS) dominates some Pareto solutions then Add S(cS) into Γ and delete the solutions dominated by it; Increment accordingly counter cΓ; Else if there is empty space in Γ then Add S(cS) into Γ. Increment accordingly counter cΓ; elitist preserving strategy // Determine the two elite Pareto solutions in Γ;

( a )

 a Index P: denoting the number of the different Pareto solutions generated by a heuristic over a specific test instance. (b) Index P*: denoting the number of not dominated solutions among all Pareto solutions obtained by all the heuristics. In particular, since some Pareto solutions obtained by one heuristic may be dominated by other heuristics, all the obtained solutions are compared to each other and the not dominated among them are selected.

  heuristics were coded in Borland Pascal and run on an IBM-compatible PC with the following hardware and software specifications: an AMD Dual Core 2.11 GHz processor, 2.0 GB of RAM, and Microsoft Windows XP Professional operating system.

Fig. 2

 2 Fig. 2 illustrates the not dominated solutions obtained by the heuristics after a single run over the first test instance of each class of problems with n≥20. As one can see from this figure, in the case of n=20 test instance (Fig. 2(a)), the solutions obtained by PSO heuristics (▲ and ∇ ∇ ∇

  results. Fig.3depicts the optimum schedule corresponding to the first instance of the examined 10-job scheduling problem. The jobs' characteristics for this instance are given in Table

Figure 1 .

 1 Figure 1. The structure of the i-th (i=1, 2,…, Ns) individual of the k-th generation.

Figure 2 .

 2 Figure 2. Unique Pareto solutions obtained by the heuristics over the 1 st test instance of TWJCTP test beds with (a) 20-jobs, (b) 50-jobs, (c) 100-jobs, and (d) 200-jobs.

Figure 3 .

 3 Figure 3. The optimum schedule for the 10-job 1/contr/∑C i with jobs' characteristics shown in Table9.

Figure 2 :

 2 Figure 2: Unique Pareto solutions obtained by the heuristics over the 1 st test instance of TWJCTP test beds with, (a) 20-jobs, (b) 50-jobs, (c) 100-jobs, and (d) 200-jobs.

FigureFigure 3 :

 3 Figure 2(a): 20-jobs TWJCTP

. Problem representation: mapping real-valued vectors to TWJCTP solutions

	mutation operators on the selected population subset. In ES the whole population is seen as
	the parent. From this population an offspring population is generated and evaluated. The new
	S is created deterministically, either from the best members of the offspring population ((µ,
	λ)-selection), or from the union of parents and offspring ((µ+λ)-selection). Offspring are
	created using simple recombination between the alleles of the parent strings, followed by a
	self-adaptive mutation scheme based on Gaussian perturbations.
	DE, PSO, and ES are stochastic optimizers over continuous search spaces, meaning that
	they utilize real-valued vectors to represent solutions of the physical problem. While a GA
	can be found in various forms such as binary-coded, permutation-coded, or real-valued, F depending on the way it codes the solution space of the physical optimization problem. To o achieve a fair comparison between the heuristics, it was decided to develop a real-valued GA r (rGA) in this work. That is, genotypes (individual solutions in S) are floating-point vectors as
	P in the case of DE, PSO, and ES.
	e e 4For the application of these heuristics on TWJCTP one must decide how to decode the r real-valued vectors maintained and evolved (the genotypes) to actual TWJCTP solutions
	(phenotypes). For a n-job TWJCTP a candidate solution consists of a job sequence π , i.e., a R permutation of the integers 1,2,…,n, together with a compression vector y , i.e., a string of e e i v integers ] [ ] 1 [ , , n y y π π K (with ] [i
	w
	O n l
	y
	Mutation and crossover operators are used to create a trial for
	each target solution. A one-to-one comparison between targets and trials determines the new
	members in S. Similarly, PSO attempts to replace all the solutions in S with better solutions,
	by exploiting information such as the current quality of an individual, its own best quality in
	history, and the quality of its neighbours. A GA from the other site replaces only a subset of S
	using a suitable parent selection strategy. Offspring are created by applying crossover and

Table 1

 1 Let us assume a 5-job TWJCTP with the characteristics given in Table1. Furthermore, let us also assume that in some point in time the following real-valued vector was generated by a

	about here >

  To examine the performance of the heuristics on TWJCTP, multiple experiments were performed over a set of test problems with n=5, 10, 20, 50, 100 and 200 jobs. No standard TWJCTP data are reported in the literature and for this reason it was decided to proceed with the random generation of this data set. For each category of problems 10 test instance were The author will be glad to distribute this data set to any reader who is interested hoping that this will become a common test bed for TWJCTP.

	6. Computational experiments
	6.1 Data generation
	generated as in the following: for every job i J (i=1,2,…,n) four integer quantities were
	randomly drawn from discrete uniform distributions: the job's initial normal processing
	time i np ∈[1,100], an upper bound of the compression permitted for this job
	i u ∈[0.6× × × × i np ,0.9× × × × i np ], the unit cost of compressing this job i φ ∈[2,9], and a weight factor o r related to the time completion of the job i w ∈[1,15].
	P
	e
	e r
	R
	e
	v i e
	w
	O n l
	y

Table 4

 4

	about here >

Table 5

 5 Fig 2(c) mentioned above. Furthermore, some other observations for this benchmark (see Table 6) are the following: (a) the highest P* value was encountered by de2 (P*=18.4). Which means that, 18.4 solutions (in average) out the 23.6 (P index) in total, were not dominated by any other Pareto solution. (b) de2 is by far the most effective heuristic. (c) The second best performance is due to pso1 (P*=4.4).Table 7, gives a synopsis of the results shown in Tables

	< Insert Table 5 about here >
	< Insert Table 6 about here >
	F o r
	P
	e
	e r
	R
	e
	v i e
	w
	O n l
	y

); almost all of them were of very poor quality and being dominated by the other Pareto solutions. This information is illustrated more clearly in

Table 8

 8

	about here >
	< Insert Figure 3 about here >
	< Insert Table 9 about here >

Table 2 .

 2 A synopsis of the control schemes used to determine the correct settings for the heuristics' control parameters.

Table 3 .

 3 Average running times in CPU seconds on a Dual Core 2.11 GHz PC.

Table 4 .

 4 Index P: Number of unique Pareto solutions generated by the heuristics after a single run over the examined test instances.

Table 5 .

 5 Index P: Average number of unique Pareto solutions obtained after 20 runs of each heuristic over the examined test instances.

Table 6 .

 6 Index P * : Number of not dominated solutions between all Pareto solutions obtained by the algorithms. Average results over 20 runs of each algorithm for the examined test problems.

Table 7 .

 7 (a) A synopsis of the results shown in Tables

Table 8 .

 8 Optimum solutions for the test instances included in the 5-job and 10-job 1/contr/∑C i . problems.

Table 9 .

 9 Jobs' characteristics for a 10-job 1/contr/∑C i problem

	F o r
	P
	e
	e r
	R
	e
	v i e
	w
	O n l
	y

Figure 1: The structure of the i-th (i=1, 2,…

			… … …, Ns) individual of the k-th generation.
	ik x	=	4 48 47 4 K n ik ik x x 2 , , , 6 ik x 1 part -π	,	4 4 3 4 2 4 t par y -1 K n ik n ik n ik x x x + 2 2 1 , , , +
	F o r
	P
	e
		e r
			R
			e
			v i e
					w
					O n l
					y

Table 9

 9

		.
	3		6	10	1	7	4	5	8	9	2
	0	69	96 115	138	166 173	226	285	374	418

Table 1 : Jobs' characteristics for a 5-job TWJCTP.

 1

			J	i	J	2	J	3	J	4	J	5
	i np 20 6 15 10 12
	u	i	4	8	5	7	7
	i w	5 15 13 13 6
	i φ	1 2.5 1.5 1	2

Table 2 : A synopsis of the control schemes used to determine the correct settings for the heuristics' control parameters.

 2

			Heuristic
		DE	PSO	rGA
			Control parameters
	Control scheme	Crossover rate: C R Scaling factor: F	Cognitive parameter: c 1 inertia weight factor: Iw Social parameter: c 2	Crossover rate: C R Mutation rate: M R

Table 3 : Average running times in CPU seconds on a Dual Core 2.11 GHz PC

 3

	n	de1	de2	pso1	pso2	rga1	rga2	es1	es2
	5	3.4	4.0	5.1	5.4	5.7	4.6	5.5	5.1
	10	11.0	10.5	11.9	13.4	11.1	11.2	13.2	11.8
	20	26.7	24.3	29.2	26.6	27.4	28.6	28.5	28.1
	50	69.9	52.9	74.5	77.3	78.3	72.4	78.8	76.3
	100	118.2	111.6	144.6	138.8	152.6	179.4	229.7	217.5
	200	215.1	213.2	271.5	258.3	323.6	335.3	386.1	389.0

Table 4 : Index P: Number of unique Pareto solutions generated by the heuristics after a single run over the examined test instances.

 4

		DE		PSO		rGA	ES			DE	PSO		rGA	ES
	n	de1 de2 pso1 pso2 rga1 rga2 es1 es2	n	de1 de2 pso1 pso2 rga1 rga2 es1 es2
	5 1	13 14	14	14	13	14 14 13 50 1 25 18	19	27	22	19 12 14
	2	13 15	15	16	17	17 16 15		2 28 25	19	24	20	26 18 15
	3	12 15	17	16	15	13 16 17		3 18 11	20	27	21	20 20 17
	4	14 17	18	17	18	19 19 16		4 23 20	21	21	22	15 14 14
	5	17 16	16	18	16	17 18 17		5 18 28	25	33	14	23 19 16
	6	13 11	13	13	12	13 13 13		6 21 20	23	20	18	19 13 11
	7	12 12	13	13	13	13 11 13		7 20 23	22	20	20	18 18 14
	8	7	7	9	9	8	7 19	9		8 18 20	17	25	25	21 14 21
	9	13 14	15	15	13	15 15 13		9 32 23	21	19	16	17 19 20
	10 12 13	13	11	13	12 13 10		10 24 24	30	24	28	23 14 25
		126 134 143 142 138 140 154 136		227 213 217 238 206 202 161 168
	10 1	6 23	17	24	15	16 18 16 100 1 22 24	21	20	12	16 11 15
	2	11 20	18	22	22	11 17 26		2 30 30	27	16	8	18 15 13
	3	21 22	22	25	21	21 21 21		3 24 24	25	19	17	13 15 19
	4	12 13	12	14	13	13 13 14		4 33 26	23	17	12	23 15	8
	5	27 25	27	28	23	20 21 23		5 30 27	15	21	19	22 14 13
	6	16 26	24	24	22	17 18 25		6 35 14	23	23	30	26 10 10
	7	18 21	25	23	20	18 24 25		7 25 18	25	17	19	18 12 15
	8	15 20	27	23	19	14 27 24		8 35 18	18	26	23	22 14	8
	9	12 22	24	29	22	21 25 22		9 42 27	21	29	30	29 12 15
	10 18 21	27	22	14	16 17 18		10 40 22	18	19	19	15 25 13

156 213 223 234 191 167 201 214 316 230 214 207 189 202 143 129

			F o r
					P
					e
						e r
						R
						e
							v i e
	20 1	12 20	18	19	20	13 14	8 200 1 30 24 w	20	22	18	17 10 15
	2 3 4 5 6 7 8	17 20 18 15 17 24 13 17 20 18 19 19 18 23	10 24 22 21 20 16 24	18 16 25 19 16 18 20	17 17 20 13 19 16 19	15 19 19 17 13 16 19 15 19 15 13 15 19 21 14 15 18 17 20 22 12	2 27 46 3 16 24 4 34 32 5 36 22 6 33 17 O n 20 23 17 20 16 l 7 28 21 15 8 26 20 24 y 19 22 15 29 20 25 24	21 12 13 20 21 20 18	14 12 12 14 17 18 13 20 14 24 13 13 18 18 14 21 12 14 16 20 17
	9	23 16	25	23	15	18 12 19	9 42 32	21	32	11	12 17 11
	10 19 24	28	16	21	9 13 16	10 38 16	23	29	15	18 12 11
		176 196 208 190 177 159 160 156	310 253 197 238 169 167 151 139

Table 5 : Index P: Average number of unique Pareto solutions obtained after 20 runs of each heuristic over the examined test instances.

 5

		DE	PSO	rGA	ES		DE	PSO	rGA	ES
	n	de1 de2 pso1 pso2 rga1 rga2 es1 es2	n	de1 de2 pso1 pso2 rga1 rga2 es1 es2

Table 6 : Index P * : Number of not dominated solutions between all Pareto solutions obtained by the algorithms. Average results over 20 runs of each algorithm for the examined test problems.

 6

		DE		PSO	rGA	ES			DE	PSO	rGA	ES
	n	de1 de2 pso1 pso2 rga1 rga2 es1 es2	n	de1 de2 pso1 pso2 rga1 rga2 es1 es2
	5 1 12.0 12.3 13.0 13.7 11.7 12.3 13.3 13.0 50 1 0.0 16.2 6.0	2.4	1.0	3.0	2.0 0.6
	2 13.0 14.0 14.0 15.3 14.7 15.7 15.7 15.0		2 0.0 18.2 3.6	2.4	1.0	2.8	0.6 0.2
	3 6.0 14.0 15.1 14.3 13.7 14.0 13.7 13.7		3 0.0 6.4 11.0	4.4	1.0	2.0	1.6 0.2
	4 14.3 17.0 17.0 16.0 17.7 18.0 17.0 13.3		4 0.2 15.8 1.0	6.8	1.2	3.2	0.6 1.4
	5 15.3 13.3 17.0 17.0 16.7 15.3 17.3 16.8		5 0.0 19.8 9.6	4.4	1.0	2.4	0.8 0.8
	6 12.0 11.7 12.0 12.0 11.7 12.7 12.0 12.0		6 0.0 19.4 8.0	3.6	1.0	2.2	0.6 1.0
	7 11.7 12.0 12.7 13.0 11.7 12.7 12.1 13.0		7 0.0 11.2 3.6	13.8	1.2	2.4	1.2 0.8
	8 7.0 6.0	8.8	9.0	7.7	7.7	9.0 8.0		8 0.0 13.6 5.2	3.8	1.0	2.8	0.6 0.8
	9 14.0 13.0 14.0 13.3 14.3 14.0 14.7 13.1		9 0.0 9.6 10.6	2.2	1.4	2.0	1.8 1.0
	10 11.0 11.7 11.7 11.3 11.7 10.7 12.3 10.6		10 0.0 19.2 6.0	5.2	1.0	2.0	0.6 0.6
	10 1	2.0 18.4 11.0 14.8	1.4	5.8	3.0	6.6 100 1 0.2 18.4 4.4	2.8	1.4	1.8	0.4 0.8
	2	2.4 17.0 12.4 20.2	1.4	4.2	3.6	5.2		2 0.4 18.4 5.6	4.2	1.8	2.0	0.4 0.8
	3	1.6 17.2 14.2 18.6	1.4	5.6	2.8	4.2		3 0.0 13.0 3.2	7.0	1.6	2.0	0.2 0.8
	4	5.2 13.1 14.8	6.6	1.4	5.4	6.2	4.8		4 0.0 14.2 1.4	7.4	1.6	2.0	0.2 2.0
	5	2.4 21.8 11.0 15.2 11.8	2.4	5.4	7.6		5 0.0 20.4 3.6	5.6	1.6	2.0	0.6 0.8
	6	1.4 19.6 17.0 15.2	4.2	3.2	4.0	4.8		6 0.0 14.8 1.8	3.8	1.6	2.4	1.0 0.2
	7	0.8 17.4 14.4 15.6	3.4	3.8	2.2	7.8		7 0.2 20.2 4.0	3.0	1.4	2.0	0.6 2.2
	8	2.8 15.8 10.0 20.6	1.4	8.8	3.2 12.4		8 0.0 20.0 3.0	5.2	1.4	2.2	1.2 0.8
	9	0.8 19.2 22.8 21.2	2.0	3.8	4.0 10.0		9 0.0 24.2 3.4	3.4	1.2	2.4	0.2 0.6
	10 2.4 19.6 16.4 20.6	1.2	4.0	4.4	5.4		10 0.2 15.0 2.4	2.8	1.2	2.0	0.0 0.6
	20 1	0.0	4.0	11.4	3.6	1.0	1.6	1.8	0.2 200 1 1.3 17.7 2.3	6.3	0.7	2.3 0.7 0.3
	2	0.0	5.0	9.4	4.8	1.0	3.4	1.2	1.0		2 2.3 23.3 9.7	5.3	0.7	2.0 0.7 0.0
	3	0.0	9.4	5.8	7.0	1.0	2.2	0.6	1.0		3 6.0 18.7 7.7	4.0	1.0	1.3 0.3 0.3
	4	0.0 12.4 10.4	6.2	1.2	3.0	0.6	0.4		4 6.3 20.7 8.0	3.0	1.0	1.3 0.0 0.0
	5	0.0 12.6	5.8	3.2	1.2	2.4	0.8	0.0		5 1.7 21.7 1.7 10.3 1.0	1.3 0.3 0.3
	6	0.0 10.2	6.6	6.8	1.2	2.0	0.4	0.0		6 6.3 15.7 4.0	8.7	1.0	1.3 0.0 0.3
	7	0.0	8.8	5.0	3.6	1.2	6.2	0.2	2.2		7 5.0 21.7 1.3	7.7	0.7	1.3 0.0 0.3
	8	0.0	4.8	9.8	10.4	1.0	3.0	0.4	1.0		8 5.7 21.7 6.3	7.0	1.0	1.3 0.3 0.0
	9	0.0	5.6	15.4	3.2	1.0	4.8	1.2	1.8		9 4.7 19.7 7.7	4.0	1.0	1.3 0.0 0.0
	10 0.0	8.6	9.4	3.2	1.0	4.2	1.4	0.6		10 4.0 15.0 4.3 10.3 1.3	1.3 0.3 0.0

Table 7 : (a) A synopsis of the results shown in Tables 5 and 6. The values are averaged over the 10 instances of each problem's category. Numbers in brackets correspond to index P * , while those outside the brackets to index P. (b) Quality ratio P*/P.

 7

	n	de1	de2	pso1	pso2	rga1	rga2	es1	es2

Table 7 (a)

 7

	n	DE		PSO			rGA		ES
		de1	de2	pso1	pso2	rga1	rga2	es1	es2
	5	92.4	95.4	96.6	95.8	94.0	95.5	94.6	94.4
	10	13.1	85.2	60.9	71.1	16.3	25.7	19.1	30.4
	20	0.0	43.1	44.3	25.4	5.7	20.9	5.2	5.0
	50	0.1	65.7	31.1	21.1	5.4	11.5	6.5	4.5
	100	0.3	71.0	15.8	20.2	7.4	10.7	3.7	7.6
	200	14.1	75.6	26.0	30.7	5.5	8.0	1.9	1.2
	average	20.0	72.7	45.8	44.1	22.4	28.7	21.8	23.9
					Table 7(b)

Table 8 : Optimum solutions for the test instances included in the 5-job and 10-job

 8

											Page 32 of 33
	1/contr/∑ ∑ ∑ ∑C i . problems.
	Problem size					Test instances
		1	2	3	4	5	6	7	8	9	10
	5	606	381	578	511	888	477	619	821	361	511
	10	1811 1794 1994 1430 1831 2135 2153 1473 2217 2038

http://mc.manuscriptcentral.com/tprs Email: ijpr@lboro.ac.

uk International Journal of Production Research

	F o r
	P
	e
	e r
	R
	e
	v i e
	w
	O n l
	y

Table 9 :

 9 Jobs' characteristics for a 10-job 1/contr/∑ ∑ ∑ ∑C i problem.

	Jobs	i np	u	i	i φ
	1	32 23 4
	2	44 39 5
	3	96 69 10
	4	7 5 8
	5	53 40 10
	6	39 27 3
	7	28 25 7
	8	59 40 6
	9	89 78 4
	10	32 19 6

http://mc.manuscriptcentral.com/tprs Email: ijpr@lboro.ac.

uk International Journal of Production Research

http://mc.manuscriptcentral.com/tprs Email: ijpr@lboro.ac.ukInternational Journal of Production Research