Transcription
Neural networks for job-shop schedulingCitation for published version (APA):Willems, T. M., & Rooda, J. E. (1994). Neural networks for job-shop scheduling. Control Engineering Practice,2(1), 31-39. .1016/0967-0661(94)90571-1Document status and date:Published: 01/01/1994Document Version:Publisher’s PDF, also known as Version of Record (includes final page, issue and volume numbers)Please check the document version of this publication: A submitted manuscript is the version of the article upon submission and before peer-review. There can beimportant differences between the submitted version and the official published version of record. Peopleinterested in the research are advised to contact the author for the final version of the publication, or visit theDOI to the publisher's website. The final author version and the galley proof are versions of the publication after peer review. The final published version features the final layout of the paper including the volume, issue and pagenumbers.Link to publicationGeneral rightsCopyright and moral rights for the publications made accessible in the public portal are retained by the authors and/or other copyright ownersand it is a condition of accessing publications that users recognise and abide by the legal requirements associated with these rights. Users may download and print one copy of any publication from the public portal for the purpose of private study or research. You may not further distribute the material or use it for any profit-making activity or commercial gain You may freely distribute the URL identifying the publication in the public portal.If the publication is distributed under the terms of Article 25fa of the Dutch Copyright Act, indicated by the “Taverne” license above, pleasefollow below link for the End User Agreement:www.tue.nl/taverneTake down policyIf you believe that this document breaches copyright please contact us at:openaccess@tue.nlproviding details and we will investigate your claim.Download date: 12. Jul. 2022
Control Eng. Practice, Vol. 2, No. 1, pp. 31-39, 1994096%0661/94 6.00 0.00 1994 Pergamon Press LidPrinted in Great Britain. All rights reserved.NEURAL NETWORKS FOR JOB-SHOP SCHEDULINGT.M. Wiilems* and J.E. Rooda***Eindhoven University of Technology, Faculty of Mechanical Engilieering, W-hoog, Room 1.126, P.O. Box 513,5600 MB Eindhoven, The Netherlands**Eindhoven University of Technology. Faculty of Mechanical Engineering, W.hoog, Room 0.122, P.O. Box 513,5600 RIB Eindhoven, The NetherlandsAbstract. A neural network structure has been developed which is capable of solving deterministicjob-shop scheduling problems, part of the large class of np-complete problems. The problem wastranslated in an integer linear programming format which facilitated translation in an adequate neuralnetwork structure. Use of the presented structure eliminated the need for integer adjustments.Elementary precalculation is performed with the objective to reduce the search space allowing morerapid calculation of feasible solutions. In this precalculation the earliest possible starting times ofthe operations are calculated and set as tresholds in the network. The neural network structure wasreliable in simulated operation and its performance was superior to structures which have beenpresented previously. The network structure always produces feasible solutions, in less time,without the application of integer adjustments.Key Words. Job-shop scheduling, neural networks, integer linear programming, constraintsatisfaction, optimization.1. INTRODUCTIONsystem. The simple neuron-like elements (units) thatare massively connected to each other, are able toperform collective (parallel) processing. Neuralnetworks can be trained to exhibit specific behaviour(Rumelhart and McClelland, 1986), and they can alsobe predefined to perform constraint satisfaction /optimisation tasks (Hopfield and Tank, 1985). It h been shown (Foo and Takefuij, 1988a- c; van Hulle,1991) that constraint satisfaction and optimisationneural networks have the potential to solve thepredictive job-shop scheduling problem in asatisfactorily rapid manner, but the neural networkspresented in the literature all suffer, to a greater orlesser degree, from design deficiencies. If they areapplied to problems other than those for which theywere designed, they malfunction. Furthermore, someof them require an unrealistic amount of informationso that they can be fine-tuned.A job-shop is a manufacturing facility which makesuse of universal resources which can be used formany different manufacturing operations. Material tobe processed flows through the job-shop by a varietyof different routes, depending on the operations to beperformed and the sequence in which they are to beperformed. Scheduling in a job-shop is therefore aresource allocation problem which is subject toallocation and sequence constraints, an instance of theclass of np-complete problems.System engineers adopt two different approaches toscheduling: reactive and predictive scheduling. Inreactive scheduling decisions are taken at the momenta decision point is reached. It is very probable thatthis will lead to a sub-optimal solution, since thescheduler does not fully anticipate future events. Inpredictive scheduling decisions are taken in advance.This results in an optimal schedule, but unforeseensystem changes force a need for rescheduling, thusdemanding a fast scheduling method. The problemwith currently available constraint satisfactiontechniques, in this regard, is that they suffer ingeneral from combinatorial explosion, making themless suitable for np-complete problems.In this paper, a neural network structure is presentedonto which an integer linear representation of a jobshop scheduling problem can be mapped. Simulationhas shown that the network finds optimum and nearoptimum solutions. The proposed structure issuperior in the design of the feedback connections.The proposed structure guarantees feasible solutions.Due to the selected simulation approach, convergenceis deterministic. Randomness can be introduced bysimulating processing of the units in random order.A neural network is a functional abstraction of thebiological neural structures of the central nervous31
32T.M. Willems and J.E. RoodaThe search-space is truncated by precalculation andthe setting of minimum starting times (thresholds).This affects the calculation in both a positive and anegative manner: solutions are found more rapidly,but the threshold may interfere with the evolution toan optimum solution. An additional layer of unitseliminates the need for integer adjustments duringcalculation. This results in more rapid calculation ofa schedule. The selected activation function of theunits representing the calculated starting timesprohibits the calculation of negative (impossible)starting times.This paper is organised as follows: after a shortintroduction in neural network technology, the jobshop scheduling problem is introduced and explained,together with an integer linear representation of theproblem. A neural network structure capable ofsolving the scheduling problem is presented. Theproblem-specific integer linear equations can bemapped on this neural network structure, resulting ina problem specific neural network.The neural network structure is applied to a smalljob-shop scheduling problem, which is simulated,together with a more-complex problem. The small(2/3/J/Cmax) problem was solved after 42 cycleswith precalculation and 158 cycles withoutprecalculation. A larger (4/3/J/Cmax) problem wassolved in an average of 142 cycles withprecalculation and 224 cycles without precalculation.The type of activation function implemented in aunit determines the functionality of the unit. Theactivation functions used in the proposed networkstructure are described in Section 5. After thesummed input has been passed through the activationfunction, the activation (Ai) is collected by otherunits that are connected to this unit. The activationfunction may be (non)deterministic binary or(non)deterministic continuous. The activationfunction is selected according to the functionalityrequired of the neural network.Neural networks can perform two basic functions:they can be trained to remember some information(Rummelhart and McClelland, 1986), and they can beused to perform constraint satisfaction andoptimisation tasks (Hopfield and Tank, 1985; Tankand Hopfield, 1986; Poliac et al., 1987). The jobshop scheduling problem will be tackled by the lattertype.Hopfield and Tank (1985) introduced a deterministicneural network model capable of solving constraintsatisfaction and optimisation problems by translatingthe problem in a number of units with predefinedfixed weighted connections. Examples of problemsthat have been solved in this way are the 'eightqueens problem' and the 'travelling salesmanproblem' (Hopfield and Tank, 1985), crew scheduling(Poliac et al., 1987) and others.3. JOB-SHOP SCHEDULING2. NEURAL NETWORKSNeural networks may be viewed as a collection ofcommunicating simple processing elements. Theseelements are a functional abstraction of the neuronesin the central nervous system. Here the elements arecalled units, rather than 'artificial neurones' to avoidthe suggestion that any biological plausibility isclaimed.A unit is a simple processing element, connected toother units by its 'weighted' (dendritic) connections,see Fig. 1.Biag,,aFig. 1. UnitA unit collects weighted (W1 to Wn) numericalinformation from other units (A1 to An). Thisinformation, sometimes increased with a bias, issummed resulting in the net input (Ni). The Ni ispassed through an activation function F, resulting inthe activation (Ai) of the unit.A manufacturing system consists of a collection ofresources on which operations are to be performed.There are several basic resource layouts (Smit, 1992)of which the job-shop is the most flexible one. Thejob-shop contains universal resources combined witha great route flexibility. The jobs that arrive at a jobshop consist of a predescribed, rigid sequence ofoperations (recipe). Which resource an operation hasto be performed on, the allocation decision, isdetermined by the scheduler. The order in which thedifferent operations of the available jobs have to beperformed by the resources, the sequence decision, isalso determined by the scheduler. The scheduler hasto create a schedule that fulfils a specifiedperformance criterion, resulting in the optimisationof the defined manufacturing system objectives.Different manufacturing systems with differentobjectives, or even different products, require differentscheduling criteria. Several performance measuressuch as stocksize, maximum throughput, due datereliability and mean lead time, are accepted as themain scheduling performance criteria. Several othercriteria can be derived from these criteria, such asminimisation of the makespan, minimisation of themaximum lateness, or minimisation of the summedlateness. Although the machine utilisation degreeremains widely accepted as a criterion, it appears tobe only the resultant of an optimisation criterion.Which measures or derivatives are used as aperformance criterion of the scheduler, depend on themanufacturer's intentions.
33Job-Shop Scheduling/In the literature, minimisation of the makespan isoften used as the criterion, and it will also be used ascriterion in this paper. The search for an optimumschedule is bound by two types of constraints. Thefirst constraint states that the compulsory operationsequence (recipe) is to be guaranteed; the secondconstraint states that not more than one job can beprocessed on one resource at the same time.Scheduling can be viewed as optimisation, bound bysequence and resource constraints. A generaldefinition of scheduling is: scheduling is theallocation of resources over time to perform acollection of tasks (Baker, 1974).A more abstract version of the job-shop schedulingproblem is mostly encountered in the literature (e.g.Foo and Takefuji, 1988a-c; Van Hulle, 1991; Zhouet al., 1990). The general job-shop schedulingproblem, as it has been called (French, 1982), isdeterministic and no allocation decisions need to betaken. This means that for most of the job-shopscheduling problems investigated, only sequencingdecisions have to be taken, operation times aredeterministic, and no machine failure is encountered.An example of a general job-shop schedulingproblem is a job-shop with three machines that haveto operate on two jobs, all operating times andallocations being fixed. The general job-shopscheduling problem will be used in this paper toexemplify the proposed neural network.Job-shop scheduling belongs to the class of npcomplete problems. This means that the calculationeffort required to find a solution to a job-shopscheduling problems grows exponentially or fasterwith the growth of the problem size. The class of npcomplete problems contains many other problems,like the scheduling of operators to machines,managers to departments, instructors to courses,etcetera. Job-shop scheduling has been extensivelystudied partly because it is an instance of the npcomplete class of problems.Several notation systems have been presented for therepresentation of a specific job-shop schedulingproblem, with its criterion. In this paper the notationsystem of Conway et al. (1967) will be used. This isa convenient way of presenting a specific schedulingproblem in which:n number of jobsm number of machinesA operation pattern (e.g. J Job-shop)B performance criterion (e.g. Cmax minimisationof the maximum completion time, equalling theminimisation of the makespan).A two-job, three-machine, job-shop schedulingproblem with minimisation of the makespan asperformance criterion is represented as: 2131JICmax.4. INTEGER LINEAR PROGRAMMINGREPRESENTATIONDue to the difficulties encountered in solving jobshop scheduling problems, several representationalaids have been developed to facilitate schedulegeneration (Baker, 1974). Graphs and Gantt charts,for instance, are used by human schedulers. In thisarticle the Gantt chart will only be used to representthe results generated; an integer programmingapproach will be used to represent the constraints(Baker, 1974).The constraints, a predefined operation sequence(sequence constraints) and the constraint that it is notallowed to operate more than one job on one resourcethe same time (resource constraints), can be translatedto integer linear programming format in thefollowing manner. The triplet ijk will be used torepresent the operation j of job i on machine k. Foreach ijk a processing time tijk is known, and afterthe scheduling for each ijk a starting time isdetermined, denoted by Sijk. The objective of jobshop scheduling is to find a set of starting times(Sijk) which comply with the constraints,minimising the objective criterion.To represent the constraints of a job-shop schedulingproblem in an integer linear format, the sequenceconstraints have to be represented first. Suppose thatthe recipe of a job i states that operation j of job irequiring machine l is to be performed afteroperation (j-1) of job i requiring machine k isfinished. Then, for a feasible schedule, it is necessarythat Sift - Si(j- 1)k ti(j- 1)k, which can bereformulated asSift - Si(j-1)k - ti(j-1)k -0.(1)There are n(m-1) sequence equations for a n/m/J/Bjob-shop scheduling problem.The general resource constraint is of a disjunctivetype that can be represented by two equations. If job iprecedes job p on machine k then operation ijk mustbe finished before job p can be processed on machinek. Spj k Sij k tij k , which can be reformulated asSpj k - Sij k - tij k - O.(2)If, on the other hand, job p precedes job i on machinek then Sijk -Spjk tpjk, which can be reformulatedas- S p j k - tpj O.(3)Only one of these two statements is valid(disjunctive statements), depending on the (partial)schedule generated. To accommodate these twoconstraints in the representation, an indicatorvariable, Yipk, is formulated.
34T.M. Willems and J.E. RoodaThis variable indicates which statement is valid, i.e.it states whether job i precedes job p on machine k(value 1) or not (value 0). Thus the resourceconstraints become:Spj k - Sij kSijk - Spjkwith: YipkYipk H(1 - Yipk)" tijk -0 n * Yipk - tpjk -0 1 if Sijk - Spjk 0 if Sij k Spj k( )(5)The constant H should be large enough to ensure thatone of the disjunctive statements holds while at thesame time the other statement is eliminated due to H.To fulfil this requirement, H should be larger thanthe largest possible starting time difference betweentwo operations. This value can be calculated byadding all processing times (worst possible schedule):nm(6)H Ztij,.i 1 j lThere are nm(n-1) resource constraint equations for ajob-shop scheduling problem, resulting in a total ofn(mn-1) equations for a job-shop schedulingproblem. These general integer linear equationsrepresenting the constraints will be used for thetranslation of specific job-shop scheduling problemsto a format that can be mapped on a neural network.5. DESIGNING A NEURAL NETWORK FOR THEJOB-SHOP SCHEDULING PROBLEMThe integer linear representation described above hasto be translated to a neural network structure that iscapable of solving the problem. A general neuralnetwork structure is proposed, on which each specificjob-shop scheduling problem can be mapped.xAi N iThe job-shop scheduling neural network shouldcontain units that are capable of representing thestarting times of the operations (S units), whethersequence constraints are violated (SC units), whetherresource constraints are violated (RC units), and thevalue of the Yipk indicator variables (Y units).(8)Since an operation can never start before time 0, thestarting time of the entire schedule, the threshold xcan be set at 0, resulting in the implementation of anon-negativity constraint.The thresholds can also be determined in a problemspecific manner by calculation of the earliest possiblestarting time of the operations. The earliest possiblestarting time of the first operation of a job is thestarting time of the scheduled time-span: 0 in theexample. The second operation's (i (j 1) k) earliestpossible starting time is 0 tijk. The earliestpossible starting time of the third operation of job 1is 0 tijk ti (j l)k. In this manner the thresholdsof the units representing the starting time aredetermined, thus reducing the 'search space' andresulting in a more-stable network. and RC units. The net input of these units iscalculated by adding the bias to the summedincoming weighted activation:nN, Z (Wo " Ai ) B (9)j lThe bias (Bi) added to the incoming weightedactivations of the connected units is the processingtime of the operation as formulated in the equationthis unit represents. The constraint representing unitsare of a deterministic negated linear threshold typewith x being the threshold and Ni the input:x,4. - N i5.1 Units xNi xNi xNi x(lO)This activation function allows for an indication ofthe violation of the equation being represented.The bias is applied to represent the problem-specificoperation processing times.Y units. The net input of the Y units is calculatedby summation of the incoming weighted activation:/1 units. The input N i of these units is calculated byadding the previous activation Ai(t-1) (thussimulating a capacitor) to the summed incomingweighted activation.N - Z (Wo " AJ)(ll)j lThe activation is determined according to adeterministic step function:/IN i Z(Wij'Aj) Ai(,-x)(7)j--IThe selected unit for this is of a deterministic linearthreshold type with an activation A i, a threshold xand a net input N i.{ Ai N, xN, x(12)The activation of this unit represents whether job 1precedes job 2 on machine k or job 2 precedes job 1.
Job-ShopSchedulingThe proposed structure consists of three layers; thebottom layer containing the S units, the middle layercontaining the SC and RC units, and the top layercontaining the Y units. To fully represent theconstraints, weighted connections between units haveto be placed.5.2 Connections35implemented as a bias, and H as a positive ornegative weight value of the connection to Yipk.The Y units should receive information from the Sunits such that Sijk preceding Spjk results in anactivation of 1. Therefore the Sijk representing unitshould be connected with a negative (-1) weightedconnection and the Spjk representing unit with apositive ( 1) weighted connection. See Fig. 3.First the connections to the SC units will bedescribed.The constraint equation: S ijb - S i (j-1)a - t i(j.1)a -0is represented by an SC unit. The SC unit collectsthe activation (representing the Sijk) from theadequate S units of the bottom layer. To do socorrectly, the S unit representing the starting timeSijb should be connected with a weight of 1 and theS unit representing Si(j.l)a with a weight of -1. SeeFig. 2. The bias of the SC unit consists of thenegated ti(j-1)a. The received input, together with thebias of the SC unit, indicates whether the representedconstraint is violated by the suggested starting times.If the constraint is violated, the activation of the unitbecomes greater than zero. This activation should beapplied as a corrective signal for the S units; Sijbshould be increased and Si(j- 1)a should be decreased,resulting in a positive weighted (e.g. 0.1) feedbackconnection to Sijb and a negative weighted (e.g. -0.I)feedback connection to Si(j-1)a. See Fig. 2.SC unit with bias of 4 i(j4)aS i(j.1)aS (ibFig. 2. General structure for sequence constraintsFor the implementation of the resource constraints ina general unit type as described above, the value of Hshould be implemented in the bias of the RC unit.This requires a reformulation of the H containing partof the constraint equation:H(1 - Yipk) (-H * Yipk) H ,allowing the implementation of H as a bias and aweight value of the connection to the Yipk unit.Spj k - Sij k H(1 - Yipk) -tijk -0- Spjk - Sijk (-H* Yijk) H -t jJ 2 0Sqk - Spyk n * ripk(13)-trek -o- Sijk - Spjk ( H * Yijk) .d.p. . - 0(14)In this way the RC equation can be implemented in ageneral RC unit with the underlined partS ijkS pjkFig. 3. General structure for resource constraintsThe RC units should receive information from the Yunits as prescribed by the equations resulting in aconnection weight of -H for the RC unit representingthe first equation (13) and of H for the RC unitrepresenting the second (14) equation. See Fig. 3.Furthermore the RC units have to receiveinformation from the S units. The RC unitrepresenting the first equation should have a positive( 1) connection weight to the Spjk representing Sunit and a negative (-1) weighted connection to theSijk representing S unit. The RC unit representingthe second equation should have a negative (-1)connection weight to the Spjk representing S unitand a positive ( 1) weighted connection to the Sijkrepresenting S unit. This information, together withthe underlined part of the equation as a bias of therespective RC units, suffices to determine whetherthe proposed starting times violate the representedconstraint.A violated resource constraint should result in amodification of the starting times of the responsibleS units. To achieve this, the S units collect theactivation of the RC units through weightedconnections to the RC units. The sign of the weightsof these feedback connections cannot beunequivocally prescribed. If two operations arescheduled on one resource at the same time, it is noteasily determined which operation should be advancedand which operation should be delayed. Here somerules of thumb like 'shortest processing time first'can be implemented b y the correct setting of theweights. Small weights of these connectionsdiminish the chance of getting stuck in a localminimum, at the cost of longer processing times.
36T.M. WiUems and J.E. Rooda5.3 This general neural network structure will beexplained with the use of a small example.As an example a 2/3/J/Cmax scheduling problem isused with its machine allocations and operation timespresented in Tables I and 2.Table 1.Machine assignmentsTable 2.Processing timesOperationJob12123132132OperationJob1212 578329Before a dedicated neural network can be designed aninteger linear programming representation has to becreated according to the method presented. For thesequence constraints this translation results in:n(m-1) 4 sequence constraints of typeSijb - Si(j-1)a" ti(j-1)a -O,1) 122- 1112) 133- 122 3) 221- 2134) 232 - 221-5 208 207 203 20.For the resource constraints the value of the constantH must be determined. This constant should have avalue that is large enough to ensure that one of thedisjunctive statements holds and the other iseliminated so:mH 34,H 35.i 1 j lFor the example problem there are nm(n-1) 6resource constraints of typeSpjk - Sijk (-H* rijk) H .it. 0Sok- Spjk n * Yijk) - - O,5)6)7)8)9)10) 221 - 111 (-35"Y12 I) 35 - 5 0 111 - 221 ( 35* Y121) -3 0 232- 122 (-35"Yl22) 35 - 8 2 0 122 - 232 ( 35* Y122) -9 0 213 - 133 (-35"Y123) 35 - 2 20 133 - 213 ( 35* Y123) -7 20.In total there are n(nm-l) 10 equations, nm 6starting time (Sijk) variables and ran(n-I)/2 3disjunction (Yipk) variables for the 2-job, 3-machineproblem.The first layer of the neural network designed for theexample problem consists of 6 Sijk units, the secondlayer consists of 10 constraint units and the thirdlayer consists of 3 Y units. See Fig. 4.The thresholds of the S units can be determined in aproblem-specific manner. For instance the thresholdof the S unit representing the third operation of job 1( 133) can be set at 13 (t111 t122).First the example will be applied to clarify thefunctionality of the general neural network structurefor the sequence constraints. The sequence conslraintsare implemented in the general structure presented inFig. 2. The problem-specific elaboration of thisgeneral structure is presented in Fig. 4.The first unit of the second layer (representing thefirst sequence equation) for instance, collects negatedinformation (connection weight -1) from the unitrepresenting 111 and positive information (weight 1) from the unit representing 122. Together withthe bias of this unit (-5) the violation of thisconstraint can be determined. If, for instance, 111 1 and 122 2, a constraint violation should besignalled since the second operation starts before thefirst operation has ended. The net input of the firstconstraint unit, SC1 in Fig. 4, will be 2 - 1 - 5 -4, resulting in an activation of 4, signalling aviolation. This information has to be fed back to theS units to cause an appropriate change in startingtimes. For this reason, the S units collect theinformation from the SC units (see Fig. 4). Thecorresponding S units will receive this redirectinginformation resulting in an inhibition ( 4 * -1) ofthe S111 unit and an excitation ( 4 * 1) of the 122unit, thus working towards an acceptable solution. Ifthese feedback weights are set correctly, feasiblesolutions will be generated without requiting explicitinitialisation of the S units.The resource constraints are implemented in thegeneral structure presented in Fig. 3. The RC unitscollect information from the adequate S units and theY units according to the resource equations. SeeFigures 3 and 4.Suppose the starting time of operation 1 of job 1 onmachine 1 ( S l l l ) is 1, and the starting time ofoperation 2 of job 2 on machine 1 ( 221) is 2. Inthat case, unit Y121 receives a net input of -I 2 1 resulting in an activation of 1, signalling that 111 precedes operation 221. The RC unitrepresenting equation 5 receives -1 from 111,2from unit 221 and -35 from Y121. This value addedto the bias (30) of this RC unit results in a net inputof -5 resulting in an activation of 5, signalling aviolation. The 111 and 221 units receive thisactivation through their weighted feedbackconnections, resulting in an advanced starting time ofoperation 111 and a delayed starting time of operation122.The RC unit representing equation 6 receives 1 from 111, -2 from 221, and 35 from Y121. This valueadded to the bias (-3) of this RC unit results in a netinput of 31, resulting in an activation of 0.
Job-Shop Scheduling ::::::::: ""'N:::::::?" ::i",. / 377. RESULTS Y .::::: """ ::::::::::::::::::::::::::::::::::::::1 -a.I0s ,The 213/J/Cmaxproblem is solved by the proposednetwork. The (optimum) solution is obtained after 42cycles, see Fig. 5, in which k stands for machine.klk2k3 [][lllllllJ1J2Illll]llllllllllll0 2 4 6 8 10 12 14 16 18202224Fig. 4. 2/3H/Cmaxneural networkFig. 5. Optimum solution to 2/3/J/Cmax6. MODELLING AND SIMULATIONIn order to empirically determine the performance ofthe proposed structure, some job-shop schedulingproblems, including the example, have beenformulated. The designed neural networks aremodelled in the object oriented neural networkmodelling language 'Smallneurons' (Willems andRooda, 1992). The same language is used for thesimulation of the neural networks on a Sun spare IIworkstation. In simulation, a calculation cycleconsists of the processing of the units on a singleprocessor. There are three ways of simulating theprocessing of the designed parallel network structure.In the first method, the activation of the units iscalculated in a fixed order. First the activation of theS units is calculated, second the activation of the Yunits, and last the activation of the SC and RC units.This simulation method results in deterministicschedules; under the same initial conditions of the Sunits, the network always converges to the sameunique scheduling solution. The second method is bycalculating the activation of the units in a randomorder. In this way noise is introduced in the networkwhich often results in acceleration of the processing.By calculating the
3. JOB-SHOP SCHEDULING A manufacturing system consists of a collection of resources on which operations are to be performed. There are several basic resource layouts (Smit, 1992) of which the job-shop is the most flexible one. The job-shop contains universal resources combined with a great route flexibility.
