A PARALLEL GENETIC ALGORITHM CODE FOR SCHEDULING PROBLEMS Bryan A. Norman and James C. Bean Dept of Industrial and Operations Engineering The University of Michigan 1205 Beal Avenue Ann Arbor, Michigan 48109-2117 Technical Report 94-23 September 1994 Revised October 1994

A Genetic Algorithm Code for Scheduling Problems: Parallel Computing Version * Bryan A. Norman,James C. Bean Department of Industrial and Operations Engineering University of Michigan, Ann Arbor, MI 48109-2117 Version 1.2 Octoler 17. 1994 TI.s work \va- supplorted in partt ily tle Nat ionial Science Foundation under Grant DDM-9018515 and D M1)1) -9)S-1:s2 to the I' lniversity of Ilich igan. I

Contents 1 Introduction 1 2 User Manual 2 2.1 Code Location.................................. 2 2.2 Compiling and Running........................... 3 2.3 Setting Parameters....................... 5 2.4 An Example.................................. 7 3 Code Documentation 11 3.1 Basic Definitions and Data Structure.................... 11 3.2 Input Function................................ 14 3.3 Genetic Algorithm Functions......................... 17 3.4 Nlain FIllction and Utilities...................... 27

1 Introduction This report is a documentation and a user manual for the MPL code, genjssp-par, developed for finding solutions to job shop scheduling problems (JSSP). The code can be applied to JSSPs with the following complexity: 1. Non-zero ready times. 2. Due dates. 3. Job shop or open shop structure. 4. M'ultiple. non-icenlltical niaclli i.s. 5. Routing flexibility for jobs. 6. Se(luelnce cel)enclellt setu)l t ilmes. 7. Tooling constraints. Different jobs may compete for the same tool and/or the changeover from one tool to another may induce sequence dependent setup times. S. Tie ol) jective f tinctioll is a coimlination of regular measures. TI-he code p)resented here (loes not consi(ler precedence constraints among the jobs. Howevel. it can l)e modified in the Ilanner (lescribed in Norman[1994] to handle precedence constraints. It is also assullmed that settul)s only occur when there is a tooling change. lThec cod(le (ould bte readily inllofifi(ed to accommodate other types of setups by making.chiag, ii to tl chromiosolmeevaluation lfun'ction. The objective function considered ill t lie I')ogrlall is tlie isi tasi rdt(liiless illeastl. \\'ighted tardilness and more complicatted ol) jct\.c' I lI( liOll il('iiasI ( cail I'be cosi(lered by simplly mnodifying the chromosonmeevaluation'llllctioll. It is assumlled that the problem has a minimization objective. If the objecti ve is Iaia.xiiiization the following changes should be made: change the chrormosomne_evaluation fuiiction to reflect the correct objective function, sort each gelieratioll' s ol) jective flllnctioln values in descending order rather than ascending order,

modify the code sections that collect information about the best solution found and the first solution found within 5% of the lower bound. The code implements a genetic algorithm (GA) to search the problem space. The GA utilizes the random keys encoding described in Bean[1994] and a coarse-grained parallel population structure. For this particular implementation, alleles are represented by integers where the 3 least significant digits contain job number information and the fourth least significant digit contains machine assignment information. Computational tests show that genjssp.par finds good solutions, within 5% of provable lower bounds, to 300 job problems containing the previously listed complexities. See Norman and Bean[1994] and Norman[1994] for more information. 2 User Manual 2.1 Code Location The source code and other related files are placed on the anonymous FTP machine called freebie.engin.umich.edu under the directory /pub/misc/ga-sched The files have been compressed and stored in one file, named genjssp.zip, using the Unix zip utility. To retrieve these files, the user should use the ftp program on a machine with tcp/ip connectivity to the Internet. One should connect to freebie with the ftp command, and log in with accounlt lname anonymous and his/her electronic mail address as the password. In the following ftp session, the file genjssp.zip is retrieved. dexterY/ ftp freebie.engin.umich.edu Connected to knob2.engin.umich.edu. 220 knob2.engin.umich.edu FTP server (Version 5.60) ready. Name (freebie.engin.umich.edu:userid): anonymous

331 Guest login ok, send ident as password. Password: <<< Your Email Address Here >>> 230 Guest login ok, access restrictions apply. ftp> cd pub/misc/gasched 250 CWD command successful. ftp> get genjssp.zip 200 PORT command successful. 150 Opening ASCII mode data connection for genjssp.zip (29708 bytes). 226 Transfer complete. local: genjssp.zip remote: genjssp.zip 127515 bytes sent in 1 seconds (1.2e+02 Kbytes/s) ftp> quit 221 Goodbye. dexterY* Once the file genjssp.zip is retreiNved the file should be unzipped. This will place several files in the cullrent. directory inclllding: example problem data and the source code,'xaIMlIple p)araalll eter file. sallilIe wll )t t. and documtlentation for both the serial and parallel versions of the genetic algorit l1I. IThere is also a file titled FILE.INFO that contains a r nief (elsc(' i t iol of e of' cl of tli file s. 2.2 Compiling and Running I I I,, iit'.lltl c((,1( \\'as w\\itl te (ii to 1 11 onl a Mi-IasPar MP-1 lMassively Parallel Computer. I h.i' Illec.(lile' u('I I ill iI.s research ( L( lias 102)1 rI)(('essors (referred to as processor elements to P1. I\1,i ( i l l l it l ts a SI I 1) aci iltect liire and( the \variables that reside on each PE,tl I' Iertd 1 o a.s, p)ltural x variablle s. Ilte mlain d(ifference between this code and serial codes is t ha.t o I)('erat joIIS atel perfoIrmedt otl eacl chrolmosome simultaneously. Users interested in more sl)ecific information aboutt tlie MlasPar hardware and MPL programming language shouldl r efer to IasPar 1)ocumlllnlletat ioll[1991]. To produlce an executable program on a:3

MasPar machine using the optimizer option (Omax), type mpl genjssppar.m -Omax -o genjssp-par The executable genjssppar is invoked by the command genjssp_par There are two ilnput files for the program genjssp-par. The first input file, named genjssp-data, contains the job da-ta. The format for this file is as follows. The first line contains the va.lues of the total number of jobs, N., the total number of machines, M, and the total number of tools, 7. lThe next N lines contain specific data for each job. For each job i = 1,... A. this dat.a includes: job number, i, tool requirement, ti, ready time, ri, due time, di, processing time, /~. number of machines that can process the job, i777,,. and the list of maclhine nuimbeirs that can process the job, mn7j for j = 1,... nmi. The remaining 7 lines contain thle set.up times, Sk,1, for switching from tool type k to tool type I for A. = 1.... T. The input file format is given below.'.11 7' 1 tl 71I (ll 1 P n?77l,Mi, I ~... 772,n m 2) 2.) (12 1)2 711772 7722,1,...7 722,nn2 \A /\ X (1' 1) d,71. 771 1. I. 1 7 N.,, v.!'"~''''~7' *T.1'.' T i27 7'. 1 s.2 *** T. 1 ie( s(condl i Il)t file. genjssp-para'mieters. cont ains problem specific parameter settilngs for t he (IA. lliese parlalel's ale iscussdcl in more detail in Section 2.3. The order of tlle I arameters in the file genjssp-parameters should match the order found in the ( iscussion ill Sect tion 2.3..1

2.3 Setting Parameters The maximum problem and population sizes are given. They are used for dimensioning arrays. Max-jobs T'he maximullml nulmber of jobs. Max-machines The maximum number of machines. Maxpop The maximum population size. Maxtools The maximum number of tools. They are specified at the beginling of the code with #define statements (see section 3.1). If these li-mits are violated. genjssp-par termillates with a descriptive error message. In this case, the user should increase tIl( li limit(s) and recompile the code. The following are more prol)lell-specific )a.rlamneters, which are read from the input file genjssp-paranmeters. A I)rief description of each parameter is provided below, for more detailed information see Norman[1994]. totalpopsize Tle total,polllation size. Empirically 1 to 4 times the number of jobs \wo.)rks we(ll. lFo smaill lroblellls use a minimumn size of 100. Larger p)Ol)la.tioln sizes pl)odultce letter results but require longer running tinles to conl\v(rge to a solution. max-generations The Inaximlunm number of generations thlat the GA will run. - Longer runs l)ro(llce better solutions but require longer running times.. clonefrac'I lie (litest sti rteg, is illmlllemenltedl 1b copying the numberclones est solilt ionl il()l acli sa poll p l)l latio i iinto the next generation. Subpopul)lt ioi( si/.C llllllie(l I)y clone-frac yields the value for numberclones. EIll)irically a. xalue of.04 -.05 for clonefrac works well. crossover-prob The crossover prola.l)ility used in the Bernoulli crossover operator. A value of 0.7 typically performs well.

immig-frac The fraction of each subpopulation that are immigrants. Empirically vxalules in the range.02 -.03 work well. immigtype-rate The fraction of the immigrants that are not strongly biased. Empirically a value of 0.6 works well. ready-weight The biasing weight assigned to ready time. Based on empirical results, the weights for the ready time and the due time should be approximately equal. Empirically a value of 1.0 works well. due-weight The biasing weight assigned to due time. strongbiasfrac The fraction of each subpopulation that will be strongly biased initially. Emplirically a. value of.7 works well. num-subpops Tle n111111uberl of stlI)l)opulations. Empirically 4 works well. If the totalpopsize is.very large (>1024) this value could be increased. Tlere is a trade-off I)etween the benefit of having more subpopulations and the liability of the subpopulations becoming too small to sea rch effectively. commun _frac'Fli' ftlactioi of each sll)population to communicate between subpop)ula.tioins. Ellllirically values in the range.03 -.04 work well. In general. thllt( alue should be less than the value of clone-frac and (lnoiughi less that number-clones - numlbertoconmmun > 0. gento-commu n The lnumber of gcnerations between occurrences of communication between subpopullat ions. Empirically a value of 20 works well. startseed The ilnitial radll(tolll nuber seed. endseed 1 lie ( llilg randomll iuml)er seed. The GA will run (endseedstar t leed )/'20() t ill'.es. lThe( 2000 is introduced because each PE reuilres a ratd(l)oiii 1ti1n'ler seed(l aid tliere are 1024 PE's on the MasPar llmac(llil( tIe s ils thlis research (2000 was used instead of 1024 to keep t Ie vale I rou.I 1d number ). Ib-value Thle value ol a lower )oundcl (assuming the objective is minimization) for tlei( 1)rolelt11n. 6

2.4 An Example Consider the following example with 10 jobs, 2 machines, and 3 tools. The job data is provided below..' = 10. = 2 T= 3 ti ri di pi r ni? Ti n,1?t,2 1 1 4.68 2.00 1.12 1 2 2 1 1.25 2.50 0.61 2 1 3 2 1.50 2.28 1.91 2 1 2 1 2 1.75 -.12 0.43 2 1 2 2 1.99 5.13 0.77 2 6 3 2.2-1 3.89 1.05 2 1 7 3 2.49 4.27 0.49 2 1 2 S 3 2.71 6.74 2.31 2 1 2 9 2:.12 5.51 1.10 2 1 2 10 1 2.78 1.1 1 0.41'.~, =- 0.00 -1.2 = 0.68 s1.3 = 1.42 ~2.1 = 0.75'2.2 = 0.00.2,3 = 0.99:,l = 1.81.:3,2 = 1.12.3,3 = 0.00'Ille corllrespondllinlg input file fi' the job data, hlere called genjssp-data, is set up for t is prob(Ill as follows: 10 2 3 1 1 4.68 2.00 1.1 2 21 2 2 1 1.25 2.50 0.61 2 1 2 3 2 1.50 2.28 1.91 2 1 2 4 2 1.75 4.12 0.43 2 1 2 5 2 1.99 5.13 0.77 2 1 2 6 3 2.24 3.89 1.05 2 1 2 7 3 2.49 4.27 0.49 2 1 2

8 3 2.74 6.74 2.31 2 1 2 9 2 3.12 5.54 1.10 2 1 2 10 1 2.78 4.11 0.41 2 1 2 0.00 0.68 1.42 0.75 0.00 0.99 1.81 1.12 0.00 Note that the format of the data file may be such that each data element is in a separate line as long the elements are in the right order. An example input file for the GA parameters genjsspparameters, is as follows: 100 250.06.70.04.6 1.0 0.9.7 2.04 20 1 20000 11.36 Here is a saimple sessioi andl t lie correslonding output. For this example the variable print-freq was set equal to 5 all(l only the results for the first random seed are shown. For this random seed, the optimum value of 11.37 was found. Example Session. auch% genjssppar The number of jobs is 10. The total number of machines is 2. The total number of tools is 3. ---------------— GA-PARAMETER VALUES —-------------------- totalpopsize = 100 max_generations = 250 clone_frac = 0.060 crossover_prob = 0.70 immig_frac = 0.040 immigtyperate = 0.60 readyweight = 1.00 due_weight = 0.90 strong_bias_frac = 0.70 num_subpops = 2 communjfrac = 0.04 gentocommun = 20 startseed = 1 8

endseed = 20000 lb_value = 11.36 ----------------— GENERATION RESULTS —-- -------------- Generation Number Best Solution Found 5 14.36 10 13.54 15 13.54 20 13.54 25 13.54 30 12.98 35 12.98 40 12.98 45 12.98 50 11.43 55 11.43 60 11.37 65 11.37 70 11.37 75 11.37 ---------------— SUMMARY DATA —--------------- The total Dpu time = 5.05 seconds. The best solution found is 11.37 The best sol. of 11.37 found in gen 60 required 4.04 seconds. Lb+5 percent solution 11.43 found in gen 48 required 3.24 seconds. ------------ - -FINAL SOLUTON —------- Job Machine Completion Tardiness For Total Number Assignment Time This Job Tardiness 3 1 3.41 1.13 1.13 2 2 1.86 0.00 1.13 4 1 3.84 0.00 1.13 7 2 3.77 0.00 1.13 5 1 4.61 0.00 1.13 9

9 1 5.71 0.17 1.30 10 1 6.87 2.76 4.06 6 2 4.82 0.93 4.99 1 1 7.99 5.99 10.98 8 2 7.13 0.39 11.37 10

3 Code Documentation 3.1 Basic Definitions and Data Structure #include <mpl.h> #include <stdio.h> #include <math.h> #include <mplibc.h> #include <time.h> #include <stdlib.h> #include <string.h> #define Max_jobs 500 /* Max number of jobs. */ #define Maxmachines 20 /* Max number of machines. */ #define Maxpop 1025 /* Max population size. #define Maxtools 50 /* Maximum number of tools.*/ #define maxint 2147483648 /* Max integer value. /* General GA variables. */ int total_popsize; /* Total population size. */ int max.generations; /* Maximum number of gens */ int numberclones; /* No. clones in a subpop. */ float clone_frac; /* Clone frac. for each subpop. */ int numberimmig; /* No. immigrants in a subpop. */ float immigfrac; /* Immig. frac. for each subpop. */ float crossoverprob; /* Crossover probability. */ int number_jobs; /* Total number of jobs. */ int number_tools; /* Total number of tools. */ int total_number_machines; /* Total number of machs. */ int startseed,endseed; /* Random seed values. int mintarget = 0; /* Minimum target value. */ float lb_value; /* Lower bound value. */ float immigtype_rate; /* Prob. for a type of immigrant.*/ plural int rankl; /* Rank within each subpop.*/ plural int rank2; /* Rank within total pop. */ double datatorank[Maxpop+l]; /* Array which is ranked. */ /* General GA variables */ plural int chrom_alleles[3][Max_jobs+l]; /* Chromosome alleles. */ plural double chromfitness[3]; /* Actual chrom. fitness. */ plural double pseudo_chromfitness[3]; /* Pseudo-fitness for subpop rank.*/ 11

/* Subpopulation variables. */ int numsubpops; /* Number of subpops. */ int subpop_size; /* Size of each subpop. */ plural int subpop.number; /* Subpop no. for each chrom. */ float communfrac; /* Frac. of subpop to commun. */ int num_tocommun; /* No. of chrom. to commun. */ int gentocommun; /* No. of gens. until commun. */ /* Plural variables that store job data */ /* in each PE in order to improve the run time. plural float due[Max_jobs+1]; plural proctime[Max_jobs+1]; plural float ready[Maxjobs+1]; plural int tool[Maxjobs+l]; /* Variables for the chromosomeevaluation() and /* print_finalsolution() functions. */ plural int temp.alleles[Maxjobs+l]; /* Temp. array to sort RKs. */ plural float machendtime[Maxmachines+l]; /* When machine next available.*/ plural float toolavail[Maxtools+1]; /* When tool next available. */ plural int toollastmach[Maxtools+1]; /* Where a tool last used. */ plural float setupvalue[Maxtools+l][Maxtools+1]; /* Setup times. */ float setup[Maxtools+1][Maxtools+l]; /* Setup times. */ /* Biasing variables */ float readyweight; /* Ready time bias weight. */ float dueweight; /* Due time bias weight. */ float raw_bias=O; /* Raw bias. */ double adj_bias=O; /* Adjusted bias. */ float truebias[Max_jobs+l]; /* Array of adjusted biases. */ float strong_bias_frac; /* Frac. of each subpop strongly biased */ lnt strongbias; /* No. per subpop strongly biased.*/ /* Other variables. */ int job[Maxjobs+2]; /* Indices for machine array. */ int machine[2000]; /* Alternative machines for a job.*/ int bestsolution_gen=0; /* Gen. that best solution found. */ lnt lb_solution_gen=0; /* Gen. that Lb+5S/ solution found.*/ float bestsolution; /* Best solution found. */ float lb_solution; /* Lb+5% solution found. */ float lblatetem; /* Temp. var. to find lbsolution.*/ 12

float totaltime; /* Total program time. */ float total_timetolb; /* Time until Lb+5% sol. found. */ float totaltime.to.best; /* Time until best solution found.*/ int best[Maxpop+l]; /* Holds PE no. for subpop. rank. */ FILE *fpl; /* Opens the data file. */ /* Defining the structures for the data file. */ struct facilities { int tool; int index; int num_machines; float ready; float due; float proctime; }; struct facilities data[Max_jobs]; A given geI nerationr (conIlsists of totalpop-size solutions (or individuals) split into num-subpops sl lbpolplnlatioils. Each i nlli vidiual hlas information stored in three different arrays. The array chrom-alleles contains the allele values for the individual. The actual fitness is conta.in(cl in chrom-fitness aind the pseudo fitness (used to rank within the different subl)I)opulations) is cont.ained in pseudochrolmfitness. 13

3.2 Input Function The function readdata reads the problem data and GA parameters and assigns the appropriate values to singular variables. void readdata() /********************************************************/ /* The function readdata() reads in the problem data */ /* from the file genjssp_data */ /* and then creates two vectors that relate machine /* compatibility with each job. */ /********************************************************/ { int i=l,j,k=0; /* Open the job data file. fpl= fopen("genjssp_data", "r"); /* If the data file does not exist, print a message. */ if (fpl == NULL) { printf("Unable to open genjsspdata \n"); return; } /* Read in data file size variables and check that they */ /* do not exceed the defined limits. fscanf(fpl,"%d %d %d",&number_jobs,&total_number_machines,&numbertools); printf("genjssp\_par \n\n"); printf("The number of jobs is Yd.\n";numberjobs); printf ("The total number of machines is %d.\n",totalnumbermachines); printf ("The total number of tools is %d.\n\n",number_tools); if (numberj obs>Maxj obs) { printf("Error: Job Limit Exceeded.\n"); printf("Data = Yd and Limit = %d.\n",number jobs,Max_jobs); exit(1); } if(total number machines>Max_machines) { 14

printf("Error: Machine Limit Exceeded.\n"); printf("Data = /d and Limit = %d.\n",total_number_machines,Max_machines); exit(1); } if(number_tools>Max_tools) { printf("Error: Tool Limit Exceeded.\n"); printf("Data = %d and Limit = %d.\n",number_tools,Max_tools); exit(1); } /* The job data information is read in as a structure. */ /* As the data is read in, two single-column arrays, */ /* job[] and machine[] that relate machine */ /* compatibility with jobs are created. */ job[O]=0; while (i<=number_jobs) { fscanf(fpl,"Y.d%d%f%f%.f %d",&data[index,data[i].tool, &data[i].ready,&data[i].due,&data[i].proctime,&data[i].nummachines); for(j=l;j<=data[i].num_machines;j++) { fscanf (fpl, ".d",&machine [k]); k++; } job[z]=k; 1++; } /* end of while statement */ for(j=l;;<=number_tools;j++) for-(k=1;k<=number_tools;k++) fscanf (fpl, ".f",&setup [j] [k]); fclose(fpl); /* Open the GA parameters file. */ fpl= fopen("genjssp_parameters", "r"); /* If the data file does not exist, print a message. */ if (fpl == NULL) { printf("Unable to open genjssp_parameters \n"); return; } I -)

/* Read in the GA parameter data. */ fscanf(fpl, "%d%d.fY.fY.fY.f%f%f%.f.%df.d%.dd%f",&totalpopsize, &maxgenerations,&clone_frac,&crossoverprob,&immig.frac, &immigtyperate,&ready_weightdueweight,&d e &strongbias.frac,&numsubpops, &commun_frac,&gentocommun,&startseed, &endseed,&lb_value); printf ( —-------------— GA-PARAMETER VALUES —------------------— \n\n"); printf("totalpopsize = %lOd \n",total.pop.size); printf("maxgenerations = %9d \n",maxgenerations); printf("clonefrac = Y.14.3f \n",clone.frac); printf("crossoverprob =,10.2f \n",crossover_prob); printf("immig_frac = %14.3f \n",immigfrac); printf("immig.typerate = %8.2f \n",immigtyperate); printf("readyweight = %12.2f \n",ready.weight); printf("dueweight = %14.2f \n",due_weight); printf("strongbias_frac = %8.2f \n",strong.biasfrac); printf("numsubpops = %13d \n",num.subpops); printf("commun_frac = %13.2f \n",commun_frac); printf("gentocommun = %lld \n",gentocommun); printf("startseed = y,15d \n",startseed); printf("endseed =,17d \n",endseed); printf("lbvalue = %16.2f \n\n",lb_value); /* Check that the population size does not exceed its limit. */ if(total_pop_size>Max_pop) { printf("Error: Population Size Limit Exceeded.\n"); printf("Data = %d and Limit = %d.\n", total_pop_size,Maxpop); exit(1); } /* Convert percentages to integer values. The.01 is to catch round-off errors. */ subpopsizetotalpopsiznum_subpops; numberclones= clonefrac*subpop_size+.01; numberimmig = immig_frac*subpopsize+.01; strongbias = strongbias_frac*subpop_size+.01; numtocommun= commun_frac*subpopsize+.01; } I (

The function convertdata copies singular data that is needed on each PE to plural variables. void convertdata() /*********************************************************/ /* The function convertdata() converts the singular /* job data to a plural copy to reside on each PE. */ /********************************************************/ { int i,j,k; for(i=1;i<=numberjobs;i++) { ready[i]=data[i].ready; due[i]=data[i].due; proctime[i =data[i].proctime; tool [i]=data[i. tool; } for(j=l;j<=number_tools;j++) for(k=1;k<=number_tools;k++) setupvalue[j] [k]=setup[j] [k]; } 3.3 Genetic Algorithm Functions'lTrel is olne aill (C.\ I'llct ionl called genetic aind folur otheri functions referred to as initializepopulation. reproduction. communication and chromosomeevaluation. Genetic first calls initialize-population which initializes some parameters and randornly genelrates an illitil pol)llat ioli of solutions. Then, it calls iteratively reproduction w\iclh. given all iiijtial generation. reproduces a new one using the process of elitist repro(duct ion. Berulloulli crossoXer,. and the immigration operator described in NorII(mail allmd Hlall[199)l]. Comml unication is called every genltocommun generations to sliare cllrolllosollles between l lie diffteremit sulbpopulations. The function chromosonimeevaluation evaluates a solution i\vell its index in the current population. The function chromosorme-evaluation is called by initialize-population and reproduction. I

void chromosomeevaluation(m) /********************************************************/ /* The function chromosomeevaluation(m) evaluates */ /* the fitness of a chromosome. /*************************** ***************** ************/ int m; { plural int job.tosched; plural int oldtooltype[Max.machines+l],newtype[Maxmachines+l]; plural int i,mach,temp; plural float setuptime; /* Initialize. chromfitness[m] =0; for(i=0;i<=total_number.machines;i++) machendtime[i] = 0; for(i=0;i<=totalnumber.machines;i++) oldtooltype[i] = 0; for(i=l;i<=number_tools;i++) { toolavail[i]=0; toollastmach[i]=0; } /* Sort the random key values for the jobs. for (i=l;i<= numberjobs;i++) tempalleles[i] = chromalleles[m][i]+i; heapsort(numberjobs); /* Construct a semi-active schedule based on the sorted */ /* order of the random keys. for (i=l;i<=number_jobs;i++) { /* Determine the job number and machine assignment. */ /* Note that the job number information */ /* is contained in the 3 least significant digits of the allele */ /* (this needs to be increased if the job number exceeds 1000) */ /* and the machine assignment is contained in the fourth least */ /* significant digit of the allele (this could be extended if the */ /* machine number exceeds 10). temp=temp_alleles[i]%10000; mach=(temp)/1000; job_to_sched = temp-(mach)*1000; 18

/* Calculate the appropriate setup time. */ if(tool[jobtosched]==oldtooltype[mach] && toollastmach[tool[job_to_sched]]==mach) setuptime=O; else setuptime=setupvalue[oldtooltype[mach]][tool[jobtosched]]; /* Calculate the starting time and subsequent */ /* completion time for each job. */ if (machendtime[mach]<toolavail[tool[jobtosched]]) machendtime[mach]=toolavail[tool[jobtosched]]; machendt ime[mach]+=setupt ime; if (machendtime[mach]<ready[jobtosched]) machendtime[mach]=ready [jobtosched]; machendtime[mach] = toolavail[tool[jobto.sched]] = machendtime[mach] + proctime[jobtosched]; /* Update the tool indicators. */ toollastmach[tool [jobtosched ]=mach; oldtooltype[mach]=tool[jobtosched]; /* Determine the tardiness. */ if (machendtime[mach] - due[job_to_sched]>O) chrom_fitness[m] += machendtime[mach]-due[jobtosched]; } } The fun c t ion0 initialize-population cletertiiiines stibpopulation data, calculates the biasilig values for cachl jobl. aIl(l c(reates an initial gelleration of chromosomes. void initialize_population() /******************* ********/ /* The function initialize_population() initializes */ /* the chromosomes, evaluates their fitness and /* performs the necessary ranking. */ /* It also determines the bias values from */ /* their ready and due weights. */ /**********************************************************/ { int j; 1.9

/* Indicate which subpop a given processor is in. */ subpopsize=totalpopsize/num.subpops; subpop.number=iproc/subpop.size; /* Calculate the biasing values for each job. */ for (j=1;j<=numberjobs;j++) { raw.bias=(ready.weight*proc[l].ready[j]+720)+(dueweight*proc[] due[j] ); rawbias /= 240.0; true.bias[j] = pow(10.0,raw.bias); } /* Create the initial population of chromosomes. */ for (j=l;j<=number_jobs;j++) { chromalleles[0] [j] = triag(0.0,truebias[j]); if(iproc-subpopsize*subpopnumber<strong-bias) chromalleles[0][j] = (plural int)(0.5*(truebias[j])); chrom.alleles[0]] [ *= 10000; chrom.alleles[0][j] += (machine[job[j-1]+ (pick(job[j]-job[j-1])-i)])*1000; /* A check to see if the bias exceeds the feasible range */ /* for the variable type or any other data problem */ /* that would lead to a negative allele value. */ if(chrom alleles[O] [j]<0) { printf("raw.bias=.f truebias [%d]= %.f\n", rawbias,j,true.bias[j]); } chromosomeevaluation(O); /* Rank the current population. */ rank2=rankf(chromfitness[0]); /* Second, rank the subpopulations. */ pseudo.chrom.fitness[0]=1000000.0*subpop.number+chromf itness[0]; ranki = rankf(pseudochromfitness[0]); 20(

best [rank ] =iproc; } The function reproduction first, employs the elitest strategy by leaving the number-clones best solutions in each subplopulation unchanged. Second, the Bernoulli crossover operation is performed. The solutions are ranked within each subpopulation and the numberimmigrants worst solutions in each subpopulation are replaced using the immigration operator. void reproduction() /************************************************************/ /* The function reproduction() performs the generational */ /* changes for the GA. Both crossover and immigration are /* performed within this function. */ /************************************************************/ { int j; plural int crossoverpartnerl,crossover_partner2; plural float immigrationvariate; plural int tempchromalleles; plural float n; /* Select crossover partners. Notice that the numberclones */ /* pe's with the best objective function measure are */ /* cloned into the next generation (an elitest strategy). */ if(iproc-subpopnumber*subpopsize<number.clones) crossoverpartnerl=crossoverpartner2=best[iproc] else { crossoverpartnerl=pick(subpopsize)-l; crossover.partner2=pick(subpopsize)-l; crossoverpartnerl+=subpop number*subpopsize; crossoverpartner2+=subpop_number*subpopsize; crossoverpartnerl=best[crossoverpartnerl]; crossoverpartner2=best[crossover_partner2]; } /* Fetch the crossover partner's gene values and copy */ 21

/* them to the PE. The data must be stored in array */ /* positions 1 and 2 because other pe's are copying the */ /* data from array position 0. After all the data has */ /* been copied the data is moved from position 2 to */ /* position 0. */ ssrfetch(crossoverpartnerl,&chromalleles[0] [],&chrom_alleles[1][1], number_jobs*sizeof(int)); ssrfetch(crossoverpartner2,&chromalleles[0] [1],&chromalleles [2][1], numberjobs*sizeof(int)); for(j=l;j<=numberjobs;j++) chrom.alleles [0] [j]=chrom_alleles [2][j]; /* Perform Bernoulli crossover on all the pe's that are */ /* supposed to be performing it (all the pe's that */ /* do not contain clones) with probability crossoverprob. */ if (iproc-subpopnumber*subpopsize>=numberclones) for(j=l;j<=number_jobs;j++) { n = urand(); if (n>=crossoverprob); else { tempchrom_alleles=chrom_alleles[0] [j]; chromalleles[0] [j]=chrom_alleles[l] [j]; chrom_alleles[l] [j]=tempchromalleles; } /* Evaluate the solutions on each PE and retain the /* best one. chromosomeevaluation(O); chromosome_evaluation(l); if(lproc-subpop_number*subpop_size>=numberclones) { if (chrom_fitness[l] < chromfitness[0]) { for (j=l;j<=numberjobs;j++) chromalleles[] [j] = chrom_alleles[l] [j]; chrom_fitness[O] = chrom_fitness[1];

} } /* Rank the current population. */ rank2=rankf(chrom_fitness[0]); /* Second, rank the subpopulations. */ pseudochromfitness[01=1000000.0*subpopnumber+chromfitness[0]; rankl = rankf(pseudochrom_fitness[0]); best[rankl]=iproc; /* Perform the immigration operation. */ if (rankl-subpop number*subpopsize>subpopsize-numberimmig-1) { /* Determine whether the variate will be strongly */ /* biased or not. immigration_variate=urand(); if(immigrationvariate<immig.type.rate) /* Create a non-strongly biased immigrant. */ for (j=1;j<=number_jobs;j++) { chromalleles[O][j] = triag(0,truebias[j]); chromalleles[0][j]*=10000; chrom alleles[0][j] += (machine[job[j-l]+ (pick(job[j]-job[j-1])-1)])*1000; } else /* Create a strongly biased immigrant. */ for (j=1; <=number_jobs;j++) { chrom_alleles[0][j]=((plural int)(0.5*true_bias[j]))*10000; chrom_alleles[O][j] += (machine[job[j-l]+ (pick(job[j]-job[j-1] )-1)])*1000; } } } Tlil fil(tioIl con1111unlicate s'liare(s ( irsinosoiies between tlhe different subpopulatiolls aifte( a liix.e(Id 11il1er olf (lc-rat iolns. Note thiat tile sharing always occurs in the

same direction between the same two subpopulations. void communicate() /*************************************************************/ /* The function communicate() shares the best solutions /* from different subpopulations. The best */ /* numtocommun solutions */ /* from the receiving subpopulation are replaced by the best */ /* numtocommun solutions from the /* sending subpopulation. */ /*************************************************************/ plural int commun_partner,m; /* Each subpopulation i (except the first one) replaces */ /* its best num_to_commun chromosomes with the best /* num_tocommun chromosomes from population i-1. /* Subpopulation 1 replaces its best */ /* num.tocommun chromosomes with the best /* numto_commun chromosomes from population numsubpops-1.*/ if(iproc-subpop.number*subpop_size < numto_commun) { if(iproc<subpopsize) communpartner=iproc+((numsubpops-l)*subpopsize); else commun_partner=iproc-subpop_size; ssrfetch(commun_partner,&chromalleles[0] [l],&chromalleles [2 [1], numberjobs*sizeof(int)); for(m=l;m<=number_jobs;m++) chrom_alleles[0] [ml =chromalleles[2] [m]; ssrfetch(communpartner,&chrom_fitness[0],&chromfitness[2] sizeof(double)); chrom_fltness[0]=chrom_fitness[2]; pseudo.chromflitness[0]=1000000.O*subpop_number+chrom_fitness[O]; } rankl=rankf(pseudochromfitness[0]); best[rankl]=lproc; }

The function genetic runs while the stopping critera are not met (i.e., stop=O). There are three stopping criteria: the GA has run for maxgenerations number of generations, the best solution is equal to a lower bound, and the best solution has remained unchanged for 15 generations and the number-ofLclones best solutions within the entire population have the same objective function value. void genetic() /**********************************************************/ /* The function genetic() runs the GA until a stopping */ /* criterion is met. /********************************************************/ { int generation.count,stop,print.freq = 1,dputimer_reset=80; /* Initialize. */ stop = 0; generationcount = 0; printf(" —- ------- — GENERATION RESULTS —------------------— \n\n"); printf("Generation Number Best Solution Found \n"); /* Continue with new generations until a stopping */ /* criterion is met. while (1-stop) { generationcount++; /* Communicate between subpopulations when necessary. */ if(generation countgentocommun==O) communicate(); /* Reset timer when necessary. */ if(generationcount==dputimerreset*(generation count/dputimer.reset)) { totaltime+=dpuTimerElapsed(); dpuTimerStart(); } /* Perform reproduction to create a new generation. Only use */ /* the PE's that are necessary. */ if(iproc<total popsize) reproduction(); 25

/* If it is time, print the current best solution. */ if(generationcount==print_freq*(generation.count/print.freq)) if(rank2==0) { printf("%lOd",generationcount); pprintf(" %.2f \n",chrom_fitness[0]); } /* Check to see if the best solution and lower + 5% */ /* solution need to be updated. */ if(rank2==0) { if(chromfitness[0]+.0l<bestsolution) { bestsolution=reduceAddf(chromfitness[O]); bestsolution_gen=generationcount; total_timetobest=totaltime+dpuTimerElapsed(); if(chromfitness[0]+.01 < lblatetem*1.05) { lb.solution=reduceAddf(chrom.fitness[0]); lbsolutiongen=generationcount; /* Reset Iblate so only find the first sol. within 5%. */ lblatetem=0.0; totaltimetolb=total_time.tottadpuTimerElapsed(); } /* Check the stopping criteria. */ if (rank2==0) if (chromfitness[0]<=min_target) stop=l; if(generationcount >= maxgenerations) stop = 1; if(bestsolutiongen+15<=generationcount) if(generationcount>50) if(rank2==number_clones-1) if(chromfitness[0]-.01<best_solution) stop = 1; ~~~~}~~~~~~~~~~~~~ 26

3.4 Main Function and Utilities The function print-final-solution prints thle final solution to the screen. The output contains the nlachine assignlilent. (colllJ)let ionl tinme and tardiness for each job. void print_final.solution() /********************************************************/ /* The function printfinalsolution() prints out the */ /* final GA solution. */ /********************************************************/ int m; { plural int jobto_sched; plural int oldtooltype[Maxmachines],newtype[Maxmachines]; plural int i,mach,temp; plural float setuptime; plural double tardiness; /* Initialize. */ chrom_fitness[m] =0; for(i=0;i<=total_number_machines;i++) machendtime[i] = 0; for(i=0;i<=total_number_machines;i++) oldtooltype[i] = 0; for(i=l; i<=Max_tools; i++) { toolavail [i]=0; toollastmach [i] =0; } printf(" -----------------— FINAL SOLUTION —-------------------— \n\n"); pr.ntf(" Job Machine Completion Tardiness For Total \n"); printf(" Number Assignment Time This Job Tardiness\n"); /I Sort the random key values for the jobs. */ for (1=l;i<= number_jobs;i++) temp.alleles[i] = chrom_alleles[m] [i]+i; heapsort(number_jobs); /* Construct a semi-active schedule based on the sorted */ /* order of the random keys. for (i=l;l<=number_jobs;i++) { /* Determine the job number and machine assignment. */ _ 7

/* Note that the job number information */ /* is contained in the 3 least significant digits of the allele */ /* (this needs to be increased if the job number exceeds 1000) */ /* and the machine assignment is contained in the fourth least */ /* significant digit of the allele (this could be extended if the */ /* machine number exceeds 10). */ temp=temp.alleles[i]%10000; mach=(temp)/1000; jobtosched = temp-(mach)*1000; /* Calculate the appropriate setup time. if(tool[job.tosched]==oldtooltype[mach] && toollastmach[tool[jobto.sched]] ==mach) setuptime=0; else setuptime=setupvalue[oldtooltype[mach] [tool[jobtosched]]; /* Calculate the starting time and subsequent */ /* completion time for each job. */ if (machendtime[mach]<toolavail[tool[job.tosched]]) machendtime[mach]=toolavail[tool[job.tosched]]; machendtime[mach]+=setuptime; if (machendtime[mach]<ready[job_to_sched]) machendtime[mach]=ready[jobtosched]; machendtime[mach] = toolavail[tool[job tosched]] = machendtime[mach] + proctime[jobtosched]; /* Update the tool indicators. */ toollastmach[tool[jobtosched]]=mach; oldtooltype[mach]=tool[jobto.sched]; /* Determine the tardiness. */ tardiness=O; if (machendtime[mach] - due[jobtosched]>O) chrom_fitness[m]+=tardiness=machendtime[mach]-due[jobtosched]; /* Print out the info for each job. */ p_printf(" y4d Y.2d y.6.2f.%6.2f.6.2f \n", jobto_sched,ch,mmachendtime[mach],tardiness,chromfitness[m]); } 2S

} The function urand randomly gelnerates uniform (0,1) variates using the function prandom. plural float urand() /* The function urand() generates a */ /* uniform (0,1) variate. */ /********************************************************/ { plural float p; p = p_random(); p = p/maxint; return p; } The function pick randomly generates integer numbers using the function p-random. plural int pick(n) /************************************************************/ /* The function pick(n) returns an integer in the range */ /* 1 to n. /***************************/ int n; { plural int pi; plural float p2; p2 = p_random(); pi = p2*n/maxint; pl=pl+l; if (pl<1) pl = 1; if (pl>n) pl = n; return pl; } The fntion triag lrado'ly geeIa t_('s <-11n it eger tlhat is tiiagonally distributed bet h\\e'( lOviclo( i(1 d lialg \1('\'itlo i I dO( e q('(ullal to ti (il av\ ag(e.

plural int traig(lo.value,hivalue) /************************************************************/ /* The function triag(lovalue,hi.value) returns an /* integer that is triangularly distributed in the range */ /* [lo.value, hivalue]. */ float lovalue; float hivalue; { plural float tempgenel; plural int tempgene2; float midpoint; midpoint=0.5*(hi_value+lo_value); tempgenel=urand(); if(tempgenel<(float)(midpoint-lo_value)/(float)(hi.value-lo.value)) tempgene2=lo_value+psqrt(midpoint-lo_value)* p_sqrt((hi_value-lo_value)*tempgenel); else tempgene2=hi_value-p_sqrt(hi_value-midpoint)* p_sqrt((hi_value-lo_value)*(1.0-tempgenel)); return tempgene2; } 1 hi'llll(1tioll heapsort sorts thle lcarra. tcnpl._alleles in ascending order. It is called 1,\ cl roiosonme_evalu ation iIl oir1e t o soilt the raclndom key values. void heapsort(num_to_sort) /* Heapsorts the array temp_alleles[n] in increasing order. */ /* A heapsort is used because it is supposed to be the */ /* most effective on the MIMD architecture for lists */ /* with a size of a few hundred items. /******** $************************************************/ lnt num_to_sort; { plural int stop; plural int l,ir,j,i; plural lnt rra;

l=(num_to_sort >> 1) +1; ir = numto_sort; for(;;) { if(l>l) rra=temp_alleles[ —1]; else { rra=temp_alleles[ir]; temp_alleles[ir]=temp_alleles[1]; if( — ir == 1) { temp_alleles[1]=rra; return; } } i=l; j=l << 1; while (j<=ir) { if (j < ir && temp_alleles[j] < temp_alleles[j+l]) ++j; if (rra < temp_alleles[j]) { temp_alleles[i]=temp_alleles[j]; j += (i=j); } else j=ir+l; } tempalleles[i]=rra; } }'I l[( iteI'a1,l.\,M(.-SP1' n 1,1(tio( lli rankf soils pluliral dat a ill ascendillg order. It is used to sort tlie (-. llrolll(ll('.i ised l ( 11 tli( ii it il(ess. It is used fior sortiiig wvithini subpopulatiOIs (rallkl ) ald(1 Ior so'llig ti ei lltir' I)o)iilat i(o (ra1ik2). 1 ii order to sort within the Sli)bpop)lliat iolls. fitlliess is co\iverted(l to psedi(lo-fitiless Lby multiplying the subpopulationI nulmber of eachll'llll)er (1 a sllbl))popilat II!by a large constant (1000000.0 in this code) a1(d1 addliIg tlhat to 1tlie act'llal itlelss value. A sort based on plseudlo-fitness orders the:'1

chromosomes first by subpopulation and then by fitness within each subpopulation. Note that for different problenms a larger constant Inay be required depending on the range of objective function values. The main function calls readdata. genetic, prints final solution information and calls printfinalsolution. main() /********************************************************I /* Beginning of main program. */ /* */ /********************************************************/ { int i,j; int loopseed; plural unsigned int seed; readdata(); convertdata); /* Run the GA for a number of times based on the values */ /* of startseed and endseed. if(iproc<totalpopsize) for(loopseed=startseed;loopseed<=endseed;loopseed+=2000) { seed=loopseed; for(i=0;i<=nproc;i++) proc[i].seed+=proc[i].iproc; p_srandom(seed); /* Reset the timing values and the best and lower bound */ /* solution values. dpuTimerStart(); total_time=0; total_time_to_lb=O; total_time_tobest=O; bestsolution=100000; lbsolution=100000; bestsolutiongen=0; lb_solution_gen=0; lblatetem=lb_value; initialize_population();:3'2

genetic(); /* Calculate and print out the total time that the GA */ /* ran, the value of the best solution and the time /* required to find it, the time required to get within */ /* 5% of the lower bound, and the final best solution. */ printf ("\n —--------------— SUMMARY DATA —---------------------— \n\n); printf("\nThe total Dpu time = %.2f seconds.\n",total_time+dpuTimerElapsed()); rank2=rankf(chromfitness[0]); if(rank2==0) { pprintf("\nThe best solution found is %.2f\n",chrom_fitness[0]); printf("\nThe best sol. of %.2f found in gen %d ", best_solution,bestsolution.gen); printf("required %.2f seconds.\n ",totaltime.to.best); printf("\nLb+5 percent solution %.2f found in gen %d ", lb_solution,lb_solution_gen); printf("required %.2f seconds.\n ",totaltimetolb); printf("\n"); print finalsolution(O); printf("\n"); } printf("\n"); }/*end seed loop*/ }:33

REFERENCES Bean, J. C. [1994], "Genetic Algorithms and Random Keys for Sequencing and Optimization," ORSA Journal on Computing, Vol. 6, Spring 1994, 154-160. MIPL rUser Guide [1991]. Doctumient Part Numlber 9302-0101, Revision Al, MasPar Computer Corporation, Sunnyvale, CA. Norman, B. A. and. ('. Bean [199-1]. "Random Keys Genetic Algorithm for Job Shop Scheduling," Technical Report 94-5, Department of Industrial and Operations Engineering, Tniversity of NMichigan. Norman, B. A.A [1994], Fort.hcominlg Pli.D. Di)ssertation. Department of Industrial and Operat.ions EIngileerliln. Il iii \Cesitly of Iiclligalln.:s-1