This file contains procedures and data to create a set of 120 FSP test instances proposed by E. Taillard (1993), Benchmarks for basic scheduling problems, European Journal of Operational Research 64, 278-285. Last update : 2/7/1996 by Dirk C. Mattfeld (email dirk@uni-bremen.de) and Rob J.M. Vaessens (email robv@win.tue.nl). The two following tables give for each instance the optimal value (if known) or the best-known lower and upper bound on this value. In the first table the values correspond to schedules for which no restriction holds on its type; in the second table the values correspond to permutation schedules. Also for each instance its size is given and a key, which refers to the first person or group of persons who proved the lower bound or found a solution with the given upper bound; the keys are explained immediately after the second table. ALL TYPES OF SCHEDULES ALLOWED: ta001-005 1278 | 1358 | 1073 | 1292 | 1231 20 x 5 VA Ta | VA VA | VA VAV2 | VA VA | VA VA ta006-010 1193 | 1234 | 1199 | 1210 | 1103 20 x 5 VA VA | VA Va | VA VAV | VA VA | VA VAV -------------------------|-------------|-------------|-------------|------------ ta011-015 1549- 1560 | 1603- 1644 | 1450- 1486 | 1356- 1368 | 1374- 1413 20 x 10 VA VAV2 | VA VAV2 | VA VAV2 | VA VAV | VA VAV ta016-020 1347- 1369 | 1400- 1428 | 1446- 1527 | 1558- 1586 | 1525- 1559 20 x 10 VA VAV2 | VA VAV2 | VA VAV | VA VAV2 | VA VAV2 -------------------------|-------------|-------------|-------------|------------ ta021-025 2021- 2293 | 1847- 2092 | 2006- 2313 | 2001- 2223 | 2086- 2291 20 x 20 VA VAV | VA VAV | VA VAV | VA Ta | VA Ta ta026-030 1971- 2221 | 2010- 2267 | 1961- 2183 | 1941- 2227 | 1992- 2178 20 x 20 VA VAV | VA VAV | VA VAV | VA VAV | VA Ta -------------------------|-------------|-------------|-------------|------------ ta031-035 2724 | 2834 | 2612 | 2751 | 2853 50 x 5 VA Ta | VA NS | VA Va2 | VA Ta | VA VA ta036-040 2825 | 2715- 2716 | 2683 | 2542- 2545 | 2776 50 x 5 VA VAV2 | VA Va2 | VA Ta | VA Va2 | VA VAV2 -------------------------|-------------|-------------|-------------|------------ ta041-045 2970- 2991 | 2829- 2867 | 2828- 2832 | 3059- 3063 | 2935- 2976 50 x 10 VA Va | VA Va | VA VAV2 | VA Va | VA Va ta046-050 2981- 2991 | 3093 | 3001- 3026 | 2858- 2887 | 3046- 3065 50 x 10 VA VAV2 | VA Va | VA Va2 | VA Va2 | VA Va -------------------------|-------------|-------------|-------------|------------ ta051-055 3566- 3856 | 3541- 3707 | 3421- 3643 | 3401- 3731 | 3378- 3619 50 x 20 VA NS2 | VA VaNS3 | VA VaNS2 | VA Va | VA NS2 ta056-060 3511- 3687 | 3474- 3706 | 3454- 3700 | 3500- 3755 | 3521- 3767 50 x 20 VA Va | VA VaNS2 | VA NS2 | VA VaNS2 | VA NS2 -------------------------|-------------|-------------|-------------|------------ ta061-065 5493 | 5257 | 5171- 5173 | 4993 | 5244- 5247 100 x 5 VA Ta | VA Va2 | VA Va2 | VA Va2 | VA VAV2 ta066-070 5135 | 5232 | 5083 | 5442 | 5318 100 x 5 VA Ta | VA VAV2 | VA Va2 | VA VAV2 | VA VAV2 -------------------------|-------------|-------------|-------------|------------ ta071-075 5759 | 5345- 5349 | 5654- 5673 | 5741- 5759 | 5432- 5455 100 x 10 VA Va2 | VA NS | VA VAV2 | VA VAV2 | VA VAV2 ta076-080 5293 | 5557- 5584 | 5604- 5617 | 5843- 5852 | 5845 100 x 10 VA VAV2 | VA VAV2 | VA Va | VA VAV2 | VA NS -------------------------|-------------|-------------|-------------|------------ ta081-085 5926- 6228 | 6122- 6210 | 6166- 6271 | 6136- 6269 | 6166- 6319 100 x 20 VA VaNS2 | VA NS2 | VA VaNS2 | VA VaNS2 | VA VaNS2 ta086-090 6203- 6403 | 6051- 6292 | 6146- 6423 | 6041- 6275 | 6381- 6434 100 x 20 VA VaNS2 | VA VaNS2 | VA NS2 | VA VaNS2 | VA VaNS2 -------------------------|-------------|-------------|-------------|------------ ta091-095 10857 | 10430-10480 | 10914-10922 | 10859-10862 | 10484-10524 200 x 10 VA VAV2 | VA Va | VA NS | VA VAV2 | VA NS ta096-100 10329 | 10836 | 10709-10727 | 10419 | 10675 200 x 10 VA Va | VA VAV2 | VA VAV2 | VA Va2 | VA Va -------------------------|-------------|-------------|-------------|------------ ta101-105 10979-11195 | 10947-11223 | 11150-11337 | 11127-11299 | 11132-11260 200 x 20 VA VaNS2 | VA VaNS2 | VA VaNS2 | VA VaNS2 | VA VaNS2 ta106-110 11085-11189 | 11194-11386 | 11126-11334 | 10965-11192 | 11122-11313 200 x 20 VA VaNS2 | VA VaNS2 | VA VaNS2 | VA VaNS2 | VA NS2 -------------------------|-------------|-------------|-------------|------------ ta111-115 25922-26059 | 26353-26520 | 26320-26371 | 26424-26456 | 26181-26334 500 x 20 VA VaNS3 | VA Va | VA Va | VA Va | VA Va ta116-120 26401-26477 | 26300-26389 | 26429-26560 | 25891-26005 | 26315-26457 500 x 20 VA Va | VA Va | VA Va | VA Va | VA Va ONLY PERMUTATION SCHEDULES ALLOWED ta001-005 1278 | 1359 | 1081 | 1293 | 1235 20 x 5 Va Ta | Va Ta | Va Ta | Va Ta | Va Ta ta006-010 1195 | 1234 | 1206 | 1230 | 1108 20 x 5 Va Ta | Va Va | Va Ta | Va Ta | Va Ta -------------------------|-------------|-------------|-------------|------------ ta011-015 1582 | 1659 | 1496 | 1377 | 1419 20 x 10 Va Ta | Va Ta | Va Ta | Va Ta | Va Ta ta016-020 1397 | 1484 | 1538 | 1593 | 1591 20 x 10 Va Ta | Va Ta | Va Ta | Va Ta | Va Ta -------------------------|-------------|-------------|-------------|------------ ta021-025 2297 | 2099 | 2326 | 2223 | 2291 20 x 20 Va Ta | Va Ta | Va Ta | Va Ta | Va Ta ta026-030 2226 | 2273 | 2200 | 2237 | 2178 20 x 20 Va Ta | Va Ta | Va Ta | Va Ta | Va Ta -------------------------|-------------|-------------|-------------|------------ ta031-035 2724 | 2834 | 2621 | 2751 | 2863 50 x 5 Va Ta | Va NS | Va Ta | Va Ta | Va Ta ta036-040 2829 | 2725 | 2683 | 2552 | 2782 50 x 5 Va Ta | Va Ta | Va Ta | Va NS | Va Ta -------------------------|-------------|-------------|-------------|------------ ta041-045 2991 | 2867 | 2839 | 3063 | 2976 50 x 10 Va Va | Va Va | Va Va | Va Va | Va Va ta046-050 3006 | 3093 | 3037 | 2897 | 3065 50 x 10 Va NS | Va Va | Va Va | Va Va | Va Va -------------------------|-------------|-------------|-------------|------------ ta051-055 3771- 3856 | 3668- 3707 | 3591- 3643 | 3635- 3731 | 3553- 3619 50 x 20 Va NS2 | Va VaNS3 | Va VaNS2 | Va Va | Va NS2 ta056-060 3667- 3687 | 3672- 3706 | 3627- 3700 | 3645- 3755 | 3696- 3767 50 x 20 Va Va | Va VaNS2 | Va NS2 | Va VaNS2 | Va NS2 -------------------------|-------------|-------------|-------------|------------ ta061-065 5493 | 5268 | 5175 | 5014 | 5250 100 x 5 Va Ta | Va NS | Va Ta | Va NS | Va Ta ta066-070 5135 | 5246 | 5094 | 5448 | 5322 100 x 5 Va Ta | Va NS | Va Ta | Va Ta | Va Va -------------------------|-------------|-------------|-------------|------------ ta071-075 5770 | 5349 | 5676 | 5781 | 5467 100 x 10 Va NS | Va NS | Va Va | Va Va | Va Va ta076-080 5303 | 5595 | 5617 | 5871 | 5845 100 x 10 Va NS | Va Va | Va Va | Va Va | Va NS -------------------------|-------------|-------------|-------------|------------ ta081-085 6106- 6228 | 6183- 6210 | 6252- 6271 | 6254- 6269 | 6262- 6319 100 x 20 Va VaNS2 | Va NS2 | Va VaNS2 | Va VaNS2 | Va VaNS2 ta086-090 6302- 6403 | 6184- 6292 | 6315- 6423 | 6204- 6275 | 6404- 6434 100 x 20 Va VaNS2 | Va VaNS2 | Va NS2 | Va VaNS2 | Va VaNS2 -------------------------|-------------|-------------|-------------|------------ ta091-095 10862 | 10480 | 10922 | 10889 | 10524 200 x 10 Va Va | Va Va | Va NS | Va NS | Va NS ta096-100 10329 | 10854 | 10730 | 10438 | 10675 200 x 10 Va Va | Va Va | Va Va | Va NS | Va Va -------------------------|-------------|-------------|-------------|------------ ta101-105 11152-11195 | 11143-11223 | 11281-11337 | 11275-11299 | 11259-11260 200 x 20 Va VaNS2 | Va VaNS2 | Va VaNS2 | Va VaNS2 | Va VaNS2 ta106-110 11176-11189 | 11337-11386 | 11301-11334 | 11145-11192 | 11284-11313 200 x 20 Va VaNS2 | Va VaNS2 | Va VaNS2 | Va VaNS2 | Va NS2 -------------------------|-------------|-------------|-------------|------------ ta111-115 26040-26059 | 26500-26520 | 26371 | 26456 | 26334 500 x 20 Va VaNS3 | Va Va | Va Va | Va Va | Va Va ta116-120 26469-26477 | 26389 | 26560 | 26005 | 26457 500 x 20 Va Va | Va Va | Va Va | Va Va | Va Va Ta: E. Taillard (1993), Benchmarks for basic scheduling problems, EJOR 64, 278-285. NS: E. Nowicki, C. Smutnicki (1996), A fast tabu search algorithm for the flow shop problem, EJOR 91, 160-175. NS2: E. Nowicki, C. Smutnicki (1996), Permutation flow shop scheduling. Benchmarks results, Report PRE 15/96, Institute of Engineering Cybernetics, Technical University of Wroclaw, Wroclaw, Poland. NS3: E. Nowicki, C. Smutnicki (1996), Personal communication. Va: R.J.M. Vaessens (1995), Personal communication. (permutation flow shop bound found by branch and bound technique) Va2: R.J.M. Vaessens (1995), Personal communication. (partial non-permutation schedule found by hand; schedule for remaining jobs found by branch and bound) VaNS2: R.J.M. Vaessens (1996), Personal communication. (permutation flow shop bound found by branch and bound technique with initial solution of NS2) VaNS3: R.J.M. Vaessens (1996), Personal communication. (permutation flow shop bound found by branch and bound technique with initial solution of NS3) VA: R.J.M. Vaessens (1995), Personal communication. (lower and upper bound found using Applegate & Cook's algorithm `edge-finder') VAV: R.J.M. Vaessens (1995), Personal communication. (upper bound found using Applegate & Cook's algorithm `shuffle' with initial solution of Va) VAV2: R.J.M. Vaessens (1995), Personal communication. (upper bound found using Applegate & Cook's algorithm `edge-finder' on partial solution abstracted from initial solution of Va) ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ In order to obtain the 120 instances ta001-ta120 choose one of the three different ways described below: o Connect to Taillard's WWW home page directly. His address is: http://www.idsia.ch/~eric/ The contents of files are self-explaining, although you may have to convert them into a machine-readable format. Obtaining the data may be a tedious work. You will find lower- and upper bounds for the problems at Taillard's WWW page too, but currently (7/96) the ones above are more up to date. o Write a PASCAL program using the procedures and seeds below. The procedures are taken from the paper "Benchmarks for Basic Scheduling Problems" directly. You have to add a main-procedure as well as a file-generation procedure yourself. ************* procedures ************** function unif(var seed : integer; low, high : integer): integer; (* generate a random number uniformly between low and high *) const m = 2147483647; a = 16807; b = 127773; c = 2836; var k : integer; value_0_1 : double; (* floating point coded on 64 bits *) begin k := seed div b ; seed := a * (seed mod b) - k * c; if seed < 0 then seed := seed + m ; value_0_1 := seed / m ; unif := low + trunc(value_0_1 * (high - low + 1)) end; procedure generate_flow_shop(var time_seed : integer; nb_jobs, nb_machines : integer; var d : matrix); (* generate the processing times d[i,j] of the ith operation of job j *) (* type matrix = array[1..20, 1..500] of integer; must be declared above *) var i, j : integer; begin for i := 1 to nb_machines do for j := 1 to nb_jobs do d[i, j] := unif(time_seed, 1, 99) end; **************** data *************** Time seed, instance 20 jobs 5 machines 873654221 ta001 379008056 ta002 1866992158 ta003 216771124 ta004 495070989 ta005 402959317 ta006 1369363414 ta007 2021925980 ta008 573109518 ta009 88325120 ta010 20 jobs 10 machines 587595453 ta011 1401007982 ta012 873136276 ta013 268827376 ta014 1634173168 ta015 691823909 ta016 73807235 ta017 1273398721 ta018 2065119309 ta019 1672900551 ta020 20 jobs 20 machines 479340445 ta021 268827376 ta022 1958948863 ta023 918272953 ta024 555010963 ta025 2010851491 ta026 1519833303 ta027 1748670931 ta028 1923497586 ta029 1829909967 ta030 50 jobs 5 machines 1328042058 ta031 200382020 ta032 496319842 ta033 1203030903 ta034 1730708564 ta035 450926852 ta036 1303135678 ta037 1273398721 ta038 587288402 ta039 248421594 ta040 50 Jobs 10 machines 1958948863 ta041 575633267 ta042 655816003 ta043 1977864101 ta044 93805469 ta045 1803345551 ta046 49612559 ta047 1899802599 ta048 2013025619 ta049 578962478 ta050 50 jobs 20 machines 1539989115 ta051 691823909 ta052 655816003 ta053 1315102446 ta054 1949668355 ta055 1923497586 ta056 1805594913 ta057 1861070898 ta058 715643788 ta059 464843328 ta060 100 jobs 5 machines 896678084 ta061 1179439976 ta062 1122278347 ta063 416756875 ta064 267829958 ta065 1835213917 ta066 1328833962 ta067 1418570761 ta068 161033112 ta069 304212574 ta070 100 jobs 10 machines 1539989115 ta071 655816003 ta072 960914243 ta073 1915696806 ta074 2013025619 ta075 1168140026 ta076 1923497586 ta077 167698528 ta078 1528387973 ta079 993794175 ta080 100 jobs 20 machines 450926852 ta081 1462772409 ta082 1021685265 ta083 83696007 ta084 508154254 ta085 1861070898 ta086 26482542 ta087 444956424 ta088 2115448041 ta089 118254244 ta090 200 jobs 10 machines 471503978 ta091 1215892992 ta092 135346136 ta093 1602504050 ta094 160037322 ta095 551454346 ta096 519485142 ta097 383947510 ta098 1968171878 ta099 540872513 ta100 200 jobs 20 machines 2013025619 ta101 475051709 ta102 914834335 ta103 810642687 ta104 1019331795 ta105 2056065863 ta106 1342855162 ta107 1325809384 ta108 1988803007 ta109 765656702 ta110 500 jobs 20 machines 1368624604 ta111 450181436 ta112 1927888393 ta113 1759567256 ta114 606425239 ta115 19268348 ta116 1298201670 ta117 2041736264 ta118 379756761 ta119 28837162 ta120 ********** verification of the first problem proposed ********* generate_flow_shop(time_seed, 20, 5, d) should provide, with time_seed = 873654221 initially : (d[i,j])= 54 83 15 71 77 36 53 38 27 87 76 91 14 29 12 77 32 87 68 94 79 3 11 99 56 70 99 60 5 56 3 61 73 75 47 14 21 86 5 77 16 89 49 15 89 45 60 23 57 64 7 1 63 41 63 47 26 75 77 40 66 58 31 68 78 91 13 59 49 85 85 9 39 41 56 40 54 77 51 31 58 56 20 85 53 35 53 41 69 13 86 72 8 49 47 87 58 18 68 28 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ o Use the C program below. It generates all 120 instance-files in one run. The first line of each instance contains the number of jobs and the number of machines. The remaining lines contain one job each, listing the machine number and processing time for each step of the job. You may choose whether the machine indices start with 0 or 1. /* Program to generate the 120 flow shop instances proposed by Taillard, E.D.: "Benchmarks for basic scheduling problems", EJOR vol. 64, pp. 278-285, 1993 Originaly written by Taillard in PASCAL, re-written in C by Dirk C. Mattfeld, University of Bremen and Rob J.M. Vaessens, Eindhoven University of Technology . Last update : 2/7/1996. UNIX compile: cc -o fsp_gen fsp_gen.c -lm Tested on the machines/systems/compilers listed below. DEC 5000 Ultrix 4.2 cc SUN 10 Solaris 2 cc IBM 6000 AIX 3.x xlc Atari ST TOS pure c IBM-PC DOS 6.2 MS-C IBM-PC Linux gcc Care should be taken on 64 bit machines (e.g. Cray). There, 'long' and 'double' contain 128 bit. In this case replace all 'long' and 'double' with the appropriate 64 bit type. Verification file 'ta001' (if VERIFY == 1 and FIRMACIND == 1) 20 5 1 54 2 79 3 16 4 66 5 58 1 83 2 3 3 89 4 58 5 56 1 15 2 11 3 49 4 31 5 20 1 71 2 99 3 15 4 68 5 85 1 77 2 56 3 89 4 78 5 53 1 36 2 70 3 45 4 91 5 35 1 53 2 99 3 60 4 13 5 53 1 38 2 60 3 23 4 59 5 41 1 27 2 5 3 57 4 49 5 69 1 87 2 56 3 64 4 85 5 13 1 76 2 3 3 7 4 85 5 86 1 91 2 61 3 1 4 9 5 72 1 14 2 73 3 63 4 39 5 8 1 29 2 75 3 41 4 41 5 49 1 12 2 47 3 63 4 56 5 47 1 77 2 14 3 47 4 40 5 87 1 32 2 21 3 26 4 54 5 58 1 87 2 86 3 75 4 77 5 18 1 68 2 5 3 77 4 51 5 68 1 94 2 77 3 40 4 31 5 28 */ #define ANSI_C 0 /* 0: K&R function style convention */ #define VERIFY 0 /* 1: produce the verification file */ #define FIRMACIND 0 /* 0,1: first machine index */ #include #include struct problem { long rand_time; /* random seed for jobs */ short num_jobs; /* number of jobs */ short num_mach; /* number of machines */ }; #if VERIFY == 1 struct problem S[] = { { 0, 0, 0}, { 873654221, 20, 5}, { 0, 0, 0}}; #else /* VERIFY */ struct problem S[] = { { 0, 0, 0}, /* 20 jobs 5 machines */ { 873654221, 20, 5}, { 379008056, 20, 5}, { 1866992158, 20, 5}, { 216771124, 20, 5}, { 495070989, 20, 5}, { 402959317, 20, 5}, { 1369363414, 20, 5}, { 2021925980, 20, 5}, { 573109518, 20, 5}, { 88325120, 20, 5}, /* 20 jobs 10 machines */ { 587595453, 20, 10}, { 1401007982, 20, 10}, { 873136276, 20, 10}, { 268827376, 20, 10}, { 1634173168, 20, 10}, { 691823909, 20, 10}, { 73807235, 20, 10}, { 1273398721, 20, 10}, { 2065119309, 20, 10}, { 1672900551, 20, 10}, /* 20 jobs 20 machines */ { 479340445, 20, 20}, { 268827376, 20, 20}, { 1958948863, 20, 20}, { 918272953, 20, 20}, { 555010963, 20, 20}, { 2010851491, 20, 20}, { 1519833303, 20, 20}, { 1748670931, 20, 20}, { 1923497586, 20, 20}, { 1829909967, 20, 20}, /* 50 jobs 5 machines */ { 1328042058, 50, 5}, { 200382020, 50, 5}, { 496319842, 50, 5}, { 1203030903, 50, 5}, { 1730708564, 50, 5}, { 450926852, 50, 5}, { 1303135678, 50, 5}, { 1273398721, 50, 5}, { 587288402, 50, 5}, { 248421594, 50, 5}, /* 50 Jobs 10 machines */ { 1958948863, 50, 10}, { 575633267, 50, 10}, { 655816003, 50, 10}, { 1977864101, 50, 10}, { 93805469, 50, 10}, { 1803345551, 50, 10}, { 49612559, 50, 10}, { 1899802599, 50, 10}, { 2013025619, 50, 10}, { 578962478, 50, 10}, /* 50 jobs 20 machines */ { 1539989115, 50, 20}, { 691823909, 50, 20}, { 655816003, 50, 20}, { 1315102446, 50, 20}, { 1949668355, 50, 20}, { 1923497586, 50, 20}, { 1805594913, 50, 20}, { 1861070898, 50, 20}, { 715643788, 50, 20}, { 464843328, 50, 20}, /* 100 jobs 5 machines */ { 896678084, 100, 5}, { 1179439976, 100, 5}, { 1122278347, 100, 5}, { 416756875, 100, 5}, { 267829958, 100, 5}, { 1835213917, 100, 5}, { 1328833962, 100, 5}, { 1418570761, 100, 5}, { 161033112, 100, 5}, { 304212574, 100, 5}, /* 100 jobs 10 machines */ { 1539989115, 100, 10}, { 655816003, 100, 10}, { 960914243, 100, 10}, { 1915696806, 100, 10}, { 2013025619, 100, 10}, { 1168140026, 100, 10}, { 1923497586, 100, 10}, { 167698528, 100, 10}, { 1528387973, 100, 10}, { 993794175, 100, 10}, /* 100 jobs 20 machines */ { 450926852, 100, 20}, { 1462772409, 100, 20}, { 1021685265, 100, 20}, { 83696007, 100, 20}, { 508154254, 100, 20}, { 1861070898, 100, 20}, { 26482542, 100, 20}, { 444956424, 100, 20}, { 2115448041, 100, 20}, { 118254244, 100, 20}, /* 200 jobs 10 machines */ { 471503978, 200, 10}, { 1215892992, 200, 10}, { 135346136, 200, 10}, { 1602504050, 200, 10}, { 160037322, 200, 10}, { 551454346, 200, 10}, { 519485142, 200, 10}, { 383947510, 200, 10}, { 1968171878, 200, 10}, { 540872513, 200, 10}, /* 200 jobs 20 machines */ { 2013025619, 200, 20}, { 475051709, 200, 20}, { 914834335, 200, 20}, { 810642687, 200, 20}, { 1019331795, 200, 20}, { 2056065863, 200, 20}, { 1342855162, 200, 20}, { 1325809384, 200, 20}, { 1988803007, 200, 20}, { 765656702, 200, 20}, /* 500 jobs 20 machines */ { 1368624604, 500, 20}, { 450181436, 500, 20}, { 1927888393, 500, 20}, { 1759567256, 500, 20}, { 606425239, 500, 20}, { 19268348, 500, 20}, { 1298201670, 500, 20}, { 2041736264, 500, 20}, { 379756761, 500, 20}, { 28837162, 500, 20}, { 0, 0, 0}}; #endif /* VERIFY */ /* generate a random number uniformly between low and high */ #if ANSI_C == 1 int unif (long *seed, short low, short high) #else short unif (seed, low, high) long *seed; short low, high; #endif { static long m = 2147483647, a = 16807, b = 127773, c = 2836; double value_0_1; long k = *seed / b; *seed = a * (*seed % b) - k * c; if(*seed < 0) *seed = *seed + m; value_0_1 = *seed / (double) m; return (short) (low + floor(value_0_1 * (high - low + 1))); } /* Maximal 500 jobs and 20 machines are provided. */ /* For larger problems extend array sizes. */ short d[21][501]; /* duration */ #if ANSI_C == 1 void generate_flow_shop(short p) /* Fill d and M according to S[p] */ #else void generate_flow_shop(p) short p; #endif { short i, j; long time_seed = S[p].rand_time; for(i = 0; i < S[p].num_mach; ++i) /* determine a random duration */ for (j = 0; j < S[p].num_jobs; ++j) /* for all operations */ d[i][j] = unif(&time_seed, 1, 99); /* 99 = max. duration of op. */ } #if ANSI_C == 1 void write_problem(short p) /* write out problem */ #else void write_problem(p) short p; #endif { short i, j; FILE *f = NULL; char name[6]; sprintf(name,"ta%03d", p); /* file name construction */ if(!(f = fopen(name,"w"))) { /* open file for writing */ fprintf(stderr,"file %s error\n", name); return; } fprintf(f,"%d %d\n", S[p].num_jobs, S[p].num_mach); /* write header line */ for(j = 0; j < S[p].num_jobs; ++j) { for(i = 0; i < S[p].num_mach; ++i) { fprintf(f,"%2d %2d ", i+FIRMACIND, d[i][j]); /* write machine and job */ } fprintf(f,"\n"); /* newline == End of job */ } fclose(f); /* close file */ } int main() { short i = 1; while(S[i].rand_time) { /* for i == 1 up to NULL entry */ generate_flow_shop(i); /* generate problem i */ write_problem(i); /* write out problem i */ ++i; /* increment i */ } return 0; } +++++++++++++++++++++++++ EOF +++++++++++++++++++++++++++++++++++++