International Journal of Production Research
`
`ISSN: 0020-7543 (Print) 1366-588X (Online) Journal homepage: https://www.tandfonline.com/loi/tprs20
`
`Scheduling/rescheduling in the manufacturing
`operating system environment
`
`M. YAMAMOTO & S. Y. NOF
`
`To cite this article: M. YAMAMOTO & S. Y. NOF (1985) Scheduling/rescheduling in the
`manufacturing operating system environment , International Journal of Production Research, 23:4,
`705-722, DOI: 10.1080/00207548508904739
`To link to this article: https://doi.org/10.1080/00207548508904739
`
`Published online: 03 Apr 2007.
`
`Submit your article to this journal
`
`Article views: 160
`
`View related articles
`
`Citing articles: 7 View citing articles
`
`Full Terms & Conditions of access and use can be found at
`https://www.tandfonline.com/action/journalInformation?journalCode=tprs20
`
`Applied Materials, Inc. Ex. 1015
`Applied v. Ocean, IPR Patent No. 6,968,248
`Page 1 of 19
`
`

`

`I~T ..1. PllOII. HES ..
`
`IHRfi.
`
`\'01.. 2:l. ~O. 4. 70:')-722
`
`Scheduling/rescheduling in the manufacturing
`operating system environmentf
`
`~1. YAMA~IOTOt and S. Y. NOF§
`
`reul-t.ime control of a
`A achedulingjrescheduling procedure is proposed for
`computerized mnnufact.u-ing facility managed by a cent.rul manufacturing
`operating system. The procedure implies schedule revisions upon significant
`operational changes such as machine breakdowns. Experiments to evaluate the
`total production time of a computerized manufacturing system with breakdowns
`under scheduling/rescheduling have yielded ndvnntages of he tween 2'5% to 7'0%
`compared to fixed sequencing nnd priority despatching procedures, respectively.
`Computation times required for the scheduling procedures on a CDC 6500/UUOO
`have also been studied. The echedullngjrescheduling procedure for an uctunl
`facility required less than two minutes, and the computation time can be
`regulated hy the selection of para meters in an approximate method ofscheduling.
`
`Introduction
`.Job shop t.ype machine scheduling problems have been well-known subjects in
`operations research for the last 25 years and extensive work about them has been
`presented (Baker 1974, Conway et al. 1967). Nevertheless.
`these theories and
`methods have scarcely been used to solve actual job shop problems in practice.
`Though the causes of this inability can he investigated from several aspects, it has
`been considered that one of the major causes is the high variability of schedule
`factors in an actual process. Significant differences can be shown hetween a schedule
`that results from traditional scheduling approaches and the real progress in a shop; .
`for example, see Bestwick and Lockyer (1979). Ifwe want to correct these differences
`und maintain control by the schedule we cannot avoid ceaseless rescheduling. Such a
`practice is usually undesirable from the standpoint of shop management and
`ndministrnt.ive cost. However, two major developments have taken place in recent
`years: computer aided scheduling and computerized manufacturing systems. This
`work develops and analyses the idea of rescheduling in the new environment of
`computerized manufacturing.
`
`Computer aided sched1ding
`Computer aided scheduling includes the following.
`
`(1) The development of interactive scheduling techniques that rely on computer
`systems, e.g., Godin (lIl78), Kerry (1980) and Hodgson and McDonnld
`(1981 ).
`(2) Scheduling with graphics capabilities, e.g., Hurrion (1978).
`
`Revision received .June 1084.
`t A shorter version of this article has appeared in .Iupanese (Yamamoto and Nof 1982).
`tCollcgc of Engineering, Hosei University, Tokyo..Japan. This research was conducted
`when Professor Yamamoto was a Research Scholar at Purdue Universit.v.
`§School of Industrial Engineering, Purdue University, West Lafayette. Indiana 4i90i,
`U.S.A.
`
`Applied Materials, Inc. Ex. 1015
`Applied v. Ocean, IPR Patent No. 6,968,248
`Page 2 of 19
`
`

`

`(3) Decision s u p l ~ o r t systems for manufacturing control, e.g., Xof and C:urecki
`( I98O).
`
`'I'hc main contrihution of such approaches is t h a t they allow non-experts to
`review and revise many schedule alternatives quickly. As a result, scheduling control
`of dynamic production systems becomes responsive and more effective.
`
`Co~~lyateriserl !?mnufaclirring systems
`T h e other major development is of computerized, or flexible, manufacturing
`systems (CMS). CMS are comprised of control computers, DNC machines, automatic
`t.ransportation and material handling facilities, automatic tool changers, etc. CMS
`provide production flexibility and programmability, and therefore h a r e been
`applied over the last decade in order to increase productivity in non-mass products.
`Imtch type production. CMS system design and the analysis of CXIS operating for
`rulcs are inrcstigzzted by many researchers (for example, sec Huzzacot and
`Shnntikuniar 1981, Nof el a/. 1978). A fundamental requirement for theeffectire use
`of CAlS is a good central control.
`
`7'he manu&cluring opernling sydfem enviroxment
`r 7 I he manufacturing operating system (MOS), was suggested by Xof, Whinston
`nnrl 13ullers (1980) for central control of automatic manufacturing. The MOS is a
`framework of multi-stage decision making in controlling the total system operation.
`T h e h108 has three main components, namely, d a t a management, logic
`management, and interfaces to hnman users and machine controllers. T h e data
`management, component is responsible for the representation, storage, and retrieval
`of d a t a uscrl for operations management decisions. The logic management compo-
`ncnt involves the representation, storage, retrieval, and execution of algorithms
`(e.g., reasoning logic) a t decision points in the system. Decision-making algorithms
`are applied for structured decision where automatic resolution is allowed. Decision
`support algorithms, on the other hand, manipulate and evaluate information t h a t is
`useful a s an aid to human decisions for non-automatic, unstructured decisions.
`Such controi is quite difficult t o achieve in a regular job shop environment. A
`CMS, however, requires significant investment cost and intensive use of computers,
`thus it is possible t o justify t h e more sophisticated and accurate shop control of the
`MOS type.
`One of the major functions of the MOS is sequencing and timing of parts
`movement, in a CMS. Since a CMS facility is a n integrated complex equipment,
`proper coordination and synchronization are paramount. Exaniples of scheduling
`,control issues are the control of the parts mix concurrently produced by t h e system;
`initial entry of parts t o the system (i.e., entry t o a n empty system after each restart);
`general enLry of parts; dynamic process selection when alternative processes are
`svailable for parts; dynamic selection of transporter and transfer route; rerouting of
`parts upon machine breakdown, and so on.
`Xof et nl. (1978) applied various heuristics for decision making in a CMS for
`priority despatching of parts in a particular CMS. An important factor in the ability
`to apply such decision making for control in a CMS is the fact t h a t operations,
`process, and transfer tiine values in t h e automatic environment are much less
`variable than in systems involving human work. This relative stability of automatic
`performance time suggests, therefore, t h a t the above-mentioned scheduling control
`
`Applied Materials, Inc. Ex. 1015
`Applied v. Ocean, IPR Patent No. 6,968,248
`Page 3 of 19
`
`

`

`Schp.duling/re,w:heduling in manufacturing operating sustems
`
`707
`
`in production
`has practical promise. On the other hand, dynamic changes
`requirements and frequent machine stoppage and breakdown complicate the eMS
`operation.
`The purpose of this article is to present a concept of scheduling/rescheduling in
`the dynamic MOS environment, and examine its feasibility and use to increase the
`CMS operational efficiency.
`
`The scheduling/rescheduling approach
`A scheduling/rescheduling approach implies that a set schedule is revised at given
`points in time due to certain significant changes in operation requirements. A
`fundamental characteristic of the scheduling/rescheduling approach is that it is not
`planned in advance for a certain future time, but
`is invoked under certain
`circumstances. An approach of this type has mainly been applied for production and
`inventory control. For example, Mather (1977), describes rescheduling in application
`of MRP. He states that MRP rescheduling procedure is called upon for a variety of
`causes, such as vendor failure to supply, unexpected scrap or spoilage, lot-size
`changes, etc.
`is considered over
`While rescheduling in production and inventory control
`periods of weeks or days, our focus is on applying the scheduling/rescheduling
`approach by the MOS more frequently if necessary, and in real-time control.
`
`General scheme
`The main feature of a scheduling/rescheduling approach is to establish a schedule
`of all operations in a system for a fixed time period in advance. The schedule is
`generated in consideration of the optimality or near optimality of the total system,
`instead of a series oflocal decisions by some priority rule applied at each machine and
`each time point. In order to realize this idea, a scheduling/rescheduling approach will
`have the following general scheme.
`
`(I) Planning phase
`(a) Part-mix assignment
`(b) Initial scheduling
`(e) Machine loading table generation
`(2) Control phase
`(a) Machine loading order instructions
`(b) Checking progress
`(c) Testing for abnormal status
`(3) Rescheduling phase
`(a) Rescheduling
`(b) Revising loading table
`(e) Resorting to control phase
`
`Each of the phases will now be described.
`
`Planning phase
`Tn the planning phase, an 'initial schedule' is generated just prior to the start of a
`new work period, based on an available production requirements data. The planning
`phase prepares all the information necessary for the operations during a given work
`period, say a work day or a shift. In the part-mix assignment the types and
`quantities of parts to be processed in the work period are decided according to the
`
`Applied Materials, Inc. Ex. 1015
`Applied v. Ocean, IPR Patent No. 6,968,248
`Page 4 of 19
`
`

`

`iOH
`
`II. Ynmnmoto and 9. Y . Xof
`
`production requirement given for this CMS. T h e p a r t - m i x assignment has t o satisfy
`
`r e q ~ ~ i r e m e ~ i t s a c c o r d i n g t o p a r t types, quantities, a n d due datesin production d u r i n g
`thesame t i m e period, i n order tonssume the proper loading foreach machine. Next, a
`schedule is generated t o process these p a r t types a n d quantities. F o r all operations
`necessary for performing jobs i n the work period, s t a r t i n g a n d finishing timeson each
`~rrncl~inearedetermined. A loading tablecan then bedeveloped for each machineand
`facility directly from the resulting schedule. I n some cases, we can assign o n l y a
`processing sequence, instead o f producing a complete timetable for each facility.
`
`Control phase
`Wext, the control phnse begins w i t h the s t a r t o f the work period. Operations are
`init,iated one b y oue following instructions from the loading tables o f the initial
`schetlele, a n d progress is checked. I f the loading table contains loading times, a
`sigt~nl is issued t o begin Lhc ncxtoperation when i t s starting t i m e i n the loading tahle
`is reached. However, if specified conditions t h a t are required t o s t a r t a n operation
`arc n o t met, e.g., n s e t temperature is n o t y e t available, this signal w i l l be held u n t i l
`Lho necessary conditionsaresatisfied. Similarly, thesignal w i l l be held i f a l l preceding
`opert~tions h a r e n o t been completed. In the case o f instructions given b y a loading
`sequence, n s i g n d 1.0 stnrt an operation is issued as soon as all precedingoperations in
`the sequence are completed a n d the specified conditions are met.
`T h e a c L d progress data o f operations are compared w i t h a current schedule
`every t i m e a new operation begins a n d finishes. I f the difference exceeds a specified
`l i m i t , the N O S w i l l decide t o enter a rescheduling phase. I n addition, certain
`a i ~ n o r m n l status n ~ l c l i as machine troubles and operator's interruptions can cause
`e n t r y into the rescheduliug phase. I n the latter situation, the rescheduling will be
`accompanied h y other nctions dcen~ed necessary t o respond t o t h e abnormal status.
`
`Kcscheduli~q phase
`III the rcscherl~~ling lrhase, the schedule times o f operations already processed, in
`
`process, o r e x p w t c d immediately t o follow i n t o processing are fixed a t firsL. T h e
`remaining operations are considered t o he free operations. F o r them, computation of
`a revised schedule is o i r r i c d out, considering the operational changes t h a t have
`triggered the rescheduli~~g. F o r instance, if a new p a r t m i x is required, then a revised
`s c l i e r l ~ ~ l e has t o be generated. In the case o f machine breakdown, the expected
`durntion o f the breakdown has t o be considered. As n result, revised loading tnhles
`arc genernted. T h e scheduling procedure itself is essentially the same as in the
`plnnning IJIIRS~,
`except t h a t the schedule o f the non-free operations is fixed.
`
`Scheduling/rescheduling experiment
`T h e sclieduling/rescl~eduling approach has heen tested o n t w o case studies o f
`t y l ~ i o d ChlSs wit,h machine l)reakdowns, a n d cornl~ared Lo operations under t w o
`scheduling techniques: one following strictly t h e sequence o f the original schedule;
`t,hc other, applying p r i o r i t y despatching rules. T h e former corresponds t o Lhe
`extreme ease t h u t M O S doesn't enter the rescheduling phase at all in the
`sche~luling/reschecluling approach. T h e latter is a traditional procedure in shop
`conLml. Figure 1 (a), ( 6 ) and (e) show the logicof the three schedulingprocedures t h a t
`h a r e heen cornpared, i.e., (a) scheduling/rescheduling; ( b ) fixed sequence; (c) p r i o r i t y
`dcspntching.
`
`Applied Materials, Inc. Ex. 1015
`Applied v. Ocean, IPR Patent No. 6,968,248
`Page 5 of 19
`
`

`

`8cheduliny/re8cheduliny in lnullujru:.lurlny opp.rnling .'i,lj8Iem8
`
`iO!!
`
`Start
`
`Generate
`Initial Schedule
`
`Occurrence of a
`machine breakdown
`
`I-
`
`machine breakdown
`data
`• where
`• when
`• duration
`
`Fix the schedule up till
`breakdown time including
`all operations already processed
`for in processing)
`
`Reschedule: Generate a
`revised schedule for all
`non-fixed operations
`
`y"
`
`more
`breakdowns?
`
`No
`
`eod
`
`Figure I (a). Logic of scheduling/rescheduling procedure.
`
`Applied Materials, Inc. Ex. 1015
`Applied v. Ocean, IPR Patent No. 6,968,248
`Page 6 of 19
`
`

`

`M . Yaninmoto and S. Y. Noj
`
`Start 0
`
`Generate
`Initial Schedule
`
`Occurrence of a
`machine breakdown
`
`duration
`
`of an operetion in pmcen on
`the bad machine by the
`breakdown duration
`
`Update the schedule time. fixing
`the sequence of operations from
`the initial rchedule
`
`breakdowns? *
`
`Figure I ( b ) . Logic of fixed-sequence procedure. Maintain the sequence from the original
`~chedule throughout all processing periods.
`
`Applied Materials, Inc. Ex. 1015
`Applied v. Ocean, IPR Patent No. 6,968,248
`Page 7 of 19
`
`

`

`where
`when
`duration
`
`Generate Initial Schedule by
`priority despatching
`
`Occurrence of a
`machine breakdown
`
`1
`
`Fix the schedule up till
`breakdom time including
`all operaions already processed
`or in processing
`
`Reschedule: generates
`red& schedule for all
`non-fixed operations
`by priority despatching
`
`Yes
`
`Figure I ( c ) .
`
`lugic of prioriLy despatching procedure. Same a9 (a), but the schedule is
`generated by priority despatching heuristics.
`
`Applied Materials, Inc. Ex. 1015
`Applied v. Ocean, IPR Patent No. 6,968,248
`Page 8 of 19
`
`

`

`i l 2
`
`111. Yo~ua~aoto and S. Y. A'oj
`
`I3y t.heso experiments we can simulate the behirviour of a shop where machine
`hrenkdowns ocalir randomly. The con~pletion time of parts in the middle of a process
`ab the tro111)led machine is prolonged, and the scheduleafter the repair Lime isaltered
`acconling t o tile respective sclleduling logics.
`\\'e hnve t.csted these procedures on tuw case studies. The first case is a small
`CAIS, which is a hypotl~etical model for ascertaining the idea of the proposed
`procedure. T h e second case is an actual CMS with six machine centres, t h e
`~:xperiment.al rlntn of which wns t.aken from one n~:tual case of the typical shop
`rct:orrls.
`
`.';chedaIieg/rexched~~Ii~~g
`algoritl~~ns
`hlost job shop scheduling tecliniques could he used for the schedoling/reschednI-
`ing. The tec1111ir~oe used ill this st.urly is the active schedule generation ( I k k e r 1974).
`r 7 I his tecllnirlue involves n tree search procedure based on a hranch-and-hound
`method. A schedule tree is produced hy the active schedule generation technique,
`whiclr ori:nt.c?l all active scherll~lc on a graph h y introducing new nrcs. Tlre arcs
`represent nr(lcr relation h e t \ r e e ~ ~ operations clue t o machine constraints. An
`objective f ~ i t ~ c t i o n defined for the search is to minimize total processing time.
`As the lower h o ~ t n d for it, we use the combination of a job-hased bound and a
`machine-hasecl hound. T h e t.rec search procedure follows the depth-first search
`m e t h o ~ l . H o u w e r , a 1)roning-uff method (dercril~ed in detail in Yamatnoto 1Bi7 a ) is
`used as iw n p l ~ r o s i m a t i o t ~ technique in order Lo regulate and limit the total
`t:nmputat,ion Lime. 'l'he pruning-otr method has heen t~pplied with b* = I where b*
`clenotes Lllc given order numhcr of a hranch, and the limitation r f step count
`searched has heen s e t at 1 =200 nodes.
`Tliesnrne nlgoritllm has l ~ e e n nl~plicd for both the initial planning phnse and the
`resche~lulitlg'l~l~ase. The program packnge, which was originally used h y Yamamoto
`( 1 9 7 7 ~ ) lrnd (I977 I)). has been ildilized with some necessary revisions on the CDC-
`(i500/(iIi00 ~ r ~ m l ~ u t c r
`at Purdtw Universit,y computer centre, as (lcscrihed h y
`\'nmarnut,(~ (1!)7!)).
`the prioril,y despntching pmr:erlurc used in the study (Fig. I (c)), the priority
`I'or
`rules Lllat 11nw heen applied are ns follows: for the entry of parts into the CMS a
`higher p r i ~ ~ r i t y was given to l n r t types t h a t require longer total processing time; for
`tAe part-to-tnnchinc a l l o c n t i o ~ ~ , which assigns parts dynamically t o 1)articular
`mechines inside the CYSI the first come first served rule was applied. These rules
`were oh~)scti a s 1,ypical of those practised at the actual CMS t h a t was t.heobject o f t h i s
`ntuily.
`
`Case I. C d l S with three nmchining centres
`The system consists of three machining centres interconnected by a recirculating
`conveyor loop nnrl a load/unloi~d station. A p a r t t o he processed is s e t 011 a n exclusive
`pallet at, t.hu Ioarling station, and sent t o the conveyor loop. T h e pallet with the part
`t.11en enters n machining centre according to the programmed instructions (loading
`t.nblt: in rnetnory) if the assigned centre is available. Otherwise, the pallet and l ~ a r t
`recirculate until an appropriate machining centre hecornes avai1al)le. Additional
`assumptions nhout the oper a t ' ton are:
`
`( I ) A p&llet ct1n hold onc item at a time.
`(2) t\ pnllct. I,ceomes free w l ~ c n pallet with a part returns hack t o a n unloacl
`station and the unloading work of the finished part is completed.
`
`Applied Materials, Inc. Ex. 1015
`Applied v. Ocean, IPR Patent No. 6,968,248
`Page 9 of 19
`
`

`

`(3) \\'hen II pallet hecomes free, if there remains a n unprocessed part of the same
`type, the pallet is loaded with the new part.
`(4) During the initial entry of parts to a n empty CNS, the part t h a t has the
`largest load on the first machine is given a highest priority. I n the case of
`using nli esclusive pallet system (i.e., different pallet types for different part
`types), theimbalanceof load between different part types isstressed, because
`parts of the same type must he processed in series 1)y the pallet restriction.
`Then this priority rule hns a n important role in the initial entry.
`
`Figure 2. Case 1: Process data for small CMS problem. (Xumber of pallets: / , = I , =
`12=1,=1,=2).
`
`I:
`
`Applied Materials, Inc. Ex. 1015
`Applied v. Ocean, IPR Patent No. 6,968,248
`Page 10 of 19
`
`

`

`The figure represents the inpot network for scheduling Lhc example case, where
`nodes are operations (loading, transporting, machining, and unloading) and arcs are
`operating sequences. Order relations dictated by pallet restrictions a r e shown by
`dotted lines in Fig. 2. For parts of the same type, it is arbitrary which particular one
`precedes the other inside t h e system from the viewpoint of scheduling. For example,
`3-4 and 20-22 for part type2. As partsof thesame part typeare freein termsof the
`proeessirig order and since there are two pallets available for part type 2, we can
`assign loading operation 3 t o precede 4 a t our option, if it is advantageous for saving
`the computation time of scquencing. In t h e scheduling algorithm, the dashed lines
`have the same meaning as regular arcs. F o r example, since part type 1 has only one
`availnhle palletl loading operation 2 of the second part type I can s t a r t only after 71
`is conipleted .
`T h e initial schedule for this case is shown in' Fig. 3 (a). The completion of all
`operation requires 8 6 time units. After starting operations according to this initial
`schedule, suplmse a machine breakdown occurs in machine I a t time 18, t h e repair of
`which is expected t o take 15 time units. Figure 3 (6) shows the change of schedule in
`the fixed sequencing case. In Fig. 3 (c) rescheduling is applied a t time 18, and the
`execution after t h a t time is carried o u t by the new schedule.
`I n order to ascertain the effect of the scheduling/rescheduling approach when
`machine breakdowns take place, we performed a computational experiment by
`generating machine breakdowns a s shown in Table I . Ten experiments were
`ponducted, each with five random breakdowns. The three scheduling procedures
`were applied in each of the ten experiments; performance in terms of A, total time
`'required t o complete all the scheduled parts, was computed.
`Averagesof total Limein each of the ten experiments, X, areshown in Fig. 4 . The
`values of initial schedules using three optional scheduling procedures increase with
`tach additional machine breakdown t h a t occurs a s time passes by. However, the
`difference in the initial schedule between the rescheduling and the priority
`despatching is retained continuously during a series of machine breakdowns, though
`there i s a tendency todecrease thisdominance as the number of machine breakdowns
`increases. The results of the fixed sequencing procedure approach those of the
`priority despatching, but the dominance is kept during the whole range of this
`experiment.
`Comparison between the scheduhg/rescheduling approach and the two other
`~ ~ r o e e d u r e s are nummarized in Table 2 (a) and (b). O u t of the 100 pair comparisons in
`Table2, thescheduling/reschednlingapproach is worse than fixed sequencing in only
`
`loading
`Ration
`
`M/C # l
`
`M/C # 2
`
`MIC # 3
`
`unloading
`station
`
`(a) lnitid schedule (olhrnd schedule)
`
`Applied Materials, Inc. Ex. 1015
`Applied v. Ocean, IPR Patent No. 6,968,248
`Page 11 of 19
`
`

`

`Srhedulinqireschedulinq in manufacturinq operating systems
`
`715
`
`loading
`station
`
`M!C #1
`
`M!C #2
`
`unloading
`station
`
`100
`(b) Fixed sequencing in case of a machine breakdown in "AI/C I at time 18.
`
`loading
`station
`
`M!C #1
`
`M!C #2
`
`M!C #3
`
`unloading
`station
`
`45
`
`o
`(r,) Rescheduling in case of the same machine breakdown.
`
`100
`
`Figure :~. The alteration of a schedule at a machine breakdown.
`
`5 cases, and worse than priority despatching in only 3 cases. Over all the experiments
`with breakdowns, the scheduling/rescheduling approach yields better performance
`than fixed scheduling by an average of about 2',5%, and better than priority
`despatching by an a\'erage of about 5'8%. The results were also compared
`statistically, since the ten experiments are random and can be considered indepen(cid:173)
`dent. (Note that results of consecutive breakdowns of the same experiment are not
`indepcndent.) Tn t-test comparisons, it was found that over the ten experiments A. RES
`was significantly better than )'FIX at a confidence level of 99% during the first a
`breakdowns, and \lfi% after the fourth breakdown, but not after the fifth breakdown.
`Compared to )'PRI>
`)'RES was
`significantly (at 99%) better during the first
`4 breakdowns, but. again not after the fifth.
`
`Ca8€ 2. GlllS with six machining centres
`The second case that was studied involves an actual eMS with six machine
`centres interconnected by a conveyor loop [Nof et al. 1978). Fifteen different part
`types are scheduled for production, each with a different quantity. The operations
`required to produce each part and the quantity required from each part type are
`described in Table S. The eMS is designed to handle up to 18 pallets simultaneously,
`either in-process at a machine, or recirculating in waiting. Since part type 3 requires
`the longest process, four pallets are assigned just for it, while all other part types are
`assigned only one pallet each.
`
`Applied Materials, Inc. Ex. 1015
`Applied v. Ocean, IPR Patent No. 6,968,248
`Page 12 of 19
`
`

`

`711;
`
`dl. Ynmarnoto rrnd S. Y . Nnf
`
`Erlariment
`~~uml,t:r Brcnkdown number
`
`Occurrence of machine
`breakdown
`
`1
`
`2
`
`3
`
`4
`
`5
`
`Total
`breakdown
`
`time
`
`hl/C number
`occurrence time
`duration
`M/C nurnlrer
`occurrence time
`durntion
`hl/C number
`occurrence time
`duration
`>I/C number
`ocei~rren(:e time
`clurntion
`M/C number
`OccIIrPeticc t,i!ue
`dnmtion
`'
`hl/C number
`occurrence time
`durntion
`hf/C number
`o c ~ u r r e n c e tilll~
`durntior~
`M/C number
`occllrrence time
`durntion
`hl/C number
`occurrence time
`duration
`hl/C number
`occurrence time
`duratior~
`
`Table I. Input of machine 1,reakrlowns for small CMS problem.
`
`F o r case 2, eight random machine breakdowns were considered, as shown in
`Tuhle 4. Tahle 4 also shows the total time, 1, required by applying each scheduling
`procedure and considering each of the breakdowns; the CPU time required for
`computation by each procedure; and comparison ratios of the different values found
`for A. i\s can beseen, in tliisexperiment the scheduling/reschedulingprocedure again
`provides better performance compared t o t h e other procedures. In this experiment
`a n advantage is found in all but one observation. On average, the scheduling/re-
`scheduling procedure yields values for A t h a t were smaller by about 3.7% compared
`tn the fixed sequence procedure, and hy about 7.0% compared t o the priority
`~lcspnt,ohing procerlure.
`
`Covrtpulnlion time requirement
`Two mnjor objections t o frequent schedule revisions during work have tradition-
`, nlly Ocen t h a t 'it is too complicated and disruptive', and t h a t it requires too much
`
`Applied Materials, Inc. Ex. 1015
`Applied v. Ocean, IPR Patent No. 6,968,248
`Page 13 of 19
`
`

`

`Scheduling/rescheduling in manufacturing operating systems
`
`717
`
`120
`
`110
`
`Schedul i ng/ Reschedul i ng
`)f-----7( Fixed Sequencing
`8
`GPriol"ity Dispatching
`
`{
`
`8O~-~--~--~--~----r­
`Initial
`2
`4
`3
`5
`schedule
`Number of machine breakdowns
`Increase of average total time by machine breakdowns.
`
`Figure 4.
`
`(a) Comparison with fixed sequencing.
`
`ARES/Am
`
`After machine breakdown number
`
`Experiment number
`
`I
`2
`3
`4
`5
`6
`7
`8
`9
`10
`Average'[
`
`Number of
`the same
`or worse
`cases
`
`0
`
`t
`
`2
`
`3
`
`4
`
`5
`
`98·0
`96'0
`100'0
`96'2
`97·9
`96'0
`98·0
`97'9
`95'7
`100'0
`97-6
`
`98'0
`96'3
`98'0
`96'2
`97'9
`98'0
`98'0
`100'0
`96·1
`100'0
`97·9
`
`98'1
`96·5
`98'0
`96'6
`100'9
`96'7
`98'2
`94'6
`98'1
`100·0
`97·8
`
`100·0
`98'2
`90'5
`96·6
`100'0
`96'7
`94'0
`100'9
`98'2
`95·0
`97·0
`
`96'7
`95·1
`90'5
`104·9
`100'8
`95'9
`89'7
`99'2
`101'8
`96·6
`97'1
`
`2
`
`2
`
`2
`
`3
`
`3
`
`t Both procedures start from a common initial schedule.
`t Total average is 97-5%: that is 2-.5% improvement.
`
`Applied Materials, Inc. Ex. 1015
`Applied v. Ocean, IPR Patent No. 6,968,248
`Page 14 of 19
`
`

`

`718
`
`d l . Yotnnmolo and S. Y. N o j
`
`( b ) Cornparison with priority despatching
`
`&w/&R,
`
`After machine breakdown number
`
`E s ~ r i m e n t number 0
`
`I
`
`2
`
`3
`
`4
`
`5
`
`Xumber of
`the same
`or worse
`UIISCY
`
`0
`
`I
`
`0
`
`I
`
`3
`
`3
`
`t ' h t n l average is 04.2%; that is 6.8% improvement.
`of sched~~li~lg/reschedulitig w i t h nlternative procedures--small CNS
`Table 2. Co~t~pnriso~ls
`problem.
`
`~ : ~ ~ m p ~ ~ t a L i o n . Since t h e first argument m a y he m u c h less significant in t h e a u t o m a t i c
`
`CNS, attention should he paid t o t h e second.
`CI'U t i m e was tnllied for co'mputation o f each schedule i n this study. In t h e first
`case study, t h e average CIJU Lime for t h e scheduling/rescheduling procedure ranged
`f r o m 12.1; seconds for t h e i n i t i a l schedule (as f o r t h e fixed sequence procedure) d o w n
`t o 0.8seconds w i t h the r a p i d decrease i n t h e sizeof t h e scheduling problem. T h e CPU
`t i m e reqnired t o o h t a i n t h e init.ial schedule for Lhe fixed sequencing procedure is the
`same as for t h e schednli~~g/resche(luling procedure. In t h i s experiment a l l scl~ednles
`IIII~. t h e i n i t i a l one required 0.8 seconds. In a practical situation, however, t h e
`
`w ~ n l ~ u t n t i o n t i m e for the schedules would n o t he necessary because t h e system
`nlwnydkccps tho given i n i t i a l sequences.
`F o r t h e p r i o r i t y despatching procedure a b o u t 0.7 seconds was required f o r each
`schednle i n t h e experiments. In the practical use of the procedure a decision b y
`p r i o r i t y rule is made a t each machine locally every t i m e a machine completes a n
`npcrntion. The number o f operation completions does n o t change by t h e machine
`brenk(lom~m, and therefore t h e t o t a l computation t i m e for scheduling hy p r i o r i t y
`despntching remains fised.
`I n the second case study, t h e size of which m a y he o f t h e order o f practical
`sit.unt,ions, Lhc C P U Lime required for t h e schetloling/resche(l~~li~~g
`procedure
`increnses. B u t , as shown i n Table 4, a revised schedule could be generated w i t h i n less
`t,h,~n t.\vo minutes. I n practical CMS operations such responses are certainly
`reasonnble. I t m u s t he p o i r ~ t e d o u t t h a t these Cl'U times are obtained under certain
`given conditionsof a n approximate method, ns mentioned hefore. \\'e stress t h a t the
`
`Applied Materials, Inc. Ex. 1015
`Applied v. Ocean, IPR Patent No. 6,968,248
`Page 15 of 19
`
`

`

`Tal~lt: 4. Cornprison of sche(l~~ling/~scheduling with alternative procedum~large CMS problem (A-Total productiun
`
`time in seconds.)
`
`time required, in minutes; t=CI'U
`
`Average:
`
`1106.4
`1 106.4
`1042.2
`1038.9
`1014.9
`964.5
`957.8
`987.3
`
`967.2
`
`.w
`
`90
`45
`
`:iO
`70
`35
`55
`60
`
`-
`
`(Initid schedule)
`
`8
`7
`ti
`5
`4
`:I
`2
`I
`
`0
`
`(%I
`Rntia
`
`despatching
`
`Priority
`
`sequence
`
`Fixed
`
`Rescheduling
`
`hlachint: bwakdown data
`
`
`
`
`
`
`
`Scheduling procedure
`
`Table 3. The problem data of Case 2.
`
`18
`4690.8 minutes
`62!)
`!)I
`
`Total number of pallets
`Total processing time
`Total number of operations
`Totnl number of parts
`
`l
`
`I
`
`I
`
`I
`
`I
`
`l
`
`L
`
`I
`
`L
`
`l
`
`L
`
`1
`
`4
`
`l
`
`L
`
`68.9 804 44.3 34.5 595 4i.3
`
`1
`
`2
`
`2
`
`2
`
`1
`
`6
`
`5
`
`5
`
`4
`
`1
`
`2
`
`1
`
`1
`
`In6 49% 42.1 446 !)37 36.9 *TO
`
`1
`
`3
`
`2
`
`9
`
`2
`
`2
`
`1
`
`2
`
`1
`
`4
`
`8
`
`6
`
`7
`
`0
`
`1
`
`36.4 13.0
`
`4
`
`9
`
`2
`
`2
`
`Xumbrr of pallets
`Quantity required
`-
`Total ~wocessine time
`Xu~nbw of prueesses
`
`Applied Materials, Inc. Ex. 1015
`Applied v. Ocean, IPR Patent No. 6,968,248
`Page 16 of 19
`
`

`

`720
`
`d l . Yaninn~olo nnd S. Y. Xoj
`
`computation time call he regulated by the selection of parameters in t h e approxi-
`mate method, according t o the speed of the specific computer and the size of
`~)rohlems in the application of this procedure.
`
`Analysis and conclusions
`The schedr~ling/rescheduling approach is defined in this article as a procedure t o
`revise a n initial scl~edule each time certainsignificant changes occur in operation
`requirements. The feasibility of this approach in the manufacturing operating
`system environment of a ChlS is also discusse