European Journal of Operational Research 139 (2002) 230–244
`
`www.elsevier.com/locate/dsw
`
`Production, Manufacturing and Logistics
`
`Using real time information for effective dynamic scheduling
`
`Peter Cowling a,*, Marcus Johansson b
`
`a Department of Computing, University of Bradford, Bradford, West Yorkshire, BD7 1DB, UK
`b Division of Manufacturing Engineering and Operations Management, University of Nottingham, Nottingham NG7 2RD, UK
`
`Received 28 February 1999; accepted 02 May 2001
`
`Abstract
`
`In many production processes real time information may be obtained from process control computers and other
`monitoring systems, but most existing scheduling models are unable to use this information to effectively influence
`scheduling decisions in real time. In this paper we develop a general framework for using real time information to
`improve scheduling decisions, which allows us to trade off the quality of the revised schedule against the production
`disturbance which results from changing the planned schedule. We illustrate how our framework can be used to select a
`strategy for using real time information for a single machine scheduling model and discuss how it may be used
`to incorporate real time information into scheduling the complex production processes of steel continuous caster
`planning. Ó 2002 Elsevier Science B.V. All rights reserved.
`
`Keywords: Scheduling; Production; Rescheduling; Real time information
`
`1. Introduction
`
`Although scheduling is a well researched area,
`and numerous articles and books have been pub-
`lished, classical scheduling theory has been little
`used in real production environments (Stoop and
`Wiers, 1996). We believe that scheduling research
`has much to offer industry and commerce, but that
`more work is needed to address the ‘‘gap’’ between
`scheduling theory and practice (MacCarthy and
`Liu, 1993). One frequent assumption of scheduling
`theory, which rarely holds in practice, is that the
`
`* Corresponding author.
`E-mail addresses: peter.cowling@scm.brad.ac.uk (P. Cowl-
`ing), marcus.b.johansson@uk.andersen.com (M. Johansson).
`
`scheduling environment is static. In many pro-
`duction and service systems, schedules must be
`revised frequently in response to both instanta-
`neous events, which occur without warning, and
`anticipated events where information is given in
`advance by, for example, process control com-
`puters or customers. In this paper we develop a
`framework for handling real time information
`concerning anticipated future events. Note that in
`this case the time of arrival of the information is
`important in deciding the best schedule revision
`strategy to adopt.
`Many manufacturing environments use an
`material requirements planning (MRP), manufac-
`turing resources planning (MRPII) or enterprise
`resources planning (ERP) system for medium term
`planning. Such a system divides the planning
`
`0377-2217/02/$ - see front matter Ó 2002 Elsevier Science B.V. All rights reserved.
`PII: S 0 3 7 7 - 2 2 1 7 ( 0 1 ) 0 0 3 5 5 - 1
`
`Applied Materials, Inc. Ex. 1018
`Applied v. Ocean, IPR Patent No. 6,968,248
`Page 1 of 15
`
`

`

`P. Cowling, M. Johansson / European Journal of Operational Research 139 (2002) 230–244
`
`231
`
`horizon into discrete time buckets and requires a
`medium term production plan for several future
`time buckets, which is used to provide due dates
`and release dates for detailed production schedul-
`ing. We gain the advantage of being able to divide
`a complex medium term capacity planning prob-
`lem into smaller and more manageable pieces at
`the cost of high rigidity in the production plan.
`The question as to how a scheduler should respond
`to changes in a dynamic system in this environ-
`ment
`is a fruitful area for research. Between
`schedule creation and execution one or several
`assumptions may have changed concerning, for
`example, machine availability or material supply.
`The obvious question is how to react to this type
`of
`information and how different
`scheduling
`strategies affect the original plan or sequence of
`jobs? To answer this question one needs to con-
`sider effects on both upstream and downstream
`operations as well as the effects on longer term
`plans. This has previously been difficult, since
`there has been a lack of real time information
`concerning system status. However, in many cur-
`rent production and service systems a great deal of
`real time information is captured for control and
`monitoring purposes. In deciding how to react we
`must consider not only the quality of the revised
`schedule but also the disruption caused by sched-
`ule revision. Our framework will consider the trade
`off between these two factors.
`Scheduling research has failed to keep pace with
`technological developments in process control and
`monitoring systems. In this paper we present a
`framework for effectively incorporating real time
`information produced by process control and
`monitoring systems into scheduling models and in
`so doing to address an important aspect of the
`‘‘gap’’ between scheduling theory and practice.
`In Section 2 we consider the types of real time
`information encountered in practice and survey
`the literature on dynamic scheduling. Here we
`present our notions of schedule repair and re-
`scheduling. In Section 3 we present two measures
`for determining the value of real time information,
`utility which measures the improvement in our
`original scheduling objectives due to schedule re-
`vision and stability which measures the disruption
`caused by schedule revision. In Sections 4 and 5 we
`
`apply our notions of utility and stability to the
`simple n=1==C single machine scheduling model.
`Section 4 investigates in detail the response of the
`model to a single piece of real time information. In
`Section 5 we carry out a simulation study to in-
`vestigate the behaviour of several strategies for
`dealing with multiple pieces of real time informa-
`tion. In Section 6 we discuss how our ideas may be
`applied to the complex scheduling environment of
`the steel continuous caster, where a great deal of
`information is produced by process control com-
`puters. Conclusions are presented in Section 7.
`
`2. Using real time data
`
`Historically, one of the major reasons for un-
`certainty in real scheduling environments has been
`the lack of accurate information (Ovacik and
`Uzsoy, 1994, 1997). However, the advent of com-
`puterised information systems capable of tracking
`job and machine status in real time has changed
`this situation. In many of the process industries,
`including the steel making example, which we will
`discuss later, information is generated in real time
`by process control computers. In discrete parts
`manufacture, computer systems for the entry and
`dissemination of data, such as VDU terminals and
`bar code scanners, are placed at various locations
`on the shop floor, to record information concern-
`ing the location and status of jobs and resources
`and to display this information for control pur-
`poses. Feedback can be generated from several or
`all work centres to track jobs and update their
`progress. This technology is now comparatively
`cheap and very effective (Singh, 1996).
`Real time information is commonly used to
`improve estimated values of some parameters,
`such as processing time or worker performance,
`based on larger sample sizes. Real time informa-
`tion is only rarely used to improve schedules and
`then only in an ad hoc manner to locally correct
`short-term problems which might arise due to
`machine failure, etc. In this paper we develop a
`systematic approach to the use of real time infor-
`mation in scheduling.
`Lindau et al. (1994) and Fredendall et al. (1996)
`have made empirical studies on the impact of real
`
`Applied Materials, Inc. Ex. 1018
`Applied v. Ocean, IPR Patent No. 6,968,248
`Page 2 of 15
`
`

`

`232
`
`P. Cowling, M. Johansson / European Journal of Operational Research 139 (2002) 230–244
`
`time information for specific industrial scheduling
`models. Both studies show that the performance of
`a system without shop floor information is inferior
`to a system where real time information is used to
`make real time scheduling decisions. Ovacik and
`Uzsoy (1994) exploit shop floor information to
`consider not only the jobs available at the machine
`at the time of the scheduling decision but also jobs
`that are going to become available within a certain
`time window. They studied a dynamic single-ma-
`chine problem with sequence-dependent set-ups by
`comparing heuristic rules that use global infor-
`mation in making local scheduling decisions at the
`machine level to several myopic dispatching rules
`which use only local information. Chang (1997)
`considered a dynamic job shop where the arrival
`and nature of jobs is governed by known proba-
`bility distributions. He showed that if estimates of
`queue length are updated in response to real time
`information, then the performance of several dis-
`patching rules could be improved.
`A dynamic scheduling system is one that uses
`real time information as it arrives. The planning
`and scheduling process then consists of one or
`more nested feedback loops, where each feedback
`loop corresponds to a scheduling period (month,
`week, day) and some group of processes which are
`undergone by the jobs. This group of processes
`might involve something as simple as being pro-
`cessed on a single machine, right up to a full
`manufacturing process. First, we formulate a static
`schedule for each period. Then we obtain real time
`information concerning, for example, the progress
`of each job and the shop floor situation, and react
`to that information to revise the schedule for the
`current period and processes, when circumstances
`make schedule changes desirable or necessary.
`Each feedback loop defines a dynamic scheduling
`problem. Each of our dynamic schedules will in-
`teract with other dynamic schedules at different
`time horizons and upstream and downstream
`processes, so that the effects of modifying a local
`schedule in response to a given piece of real time
`information must be considered throughout the
`system.
`Practical scheduling systems need to be able to
`react to significant real time events within an ac-
`ceptable response time and revise schedules ap-
`
`propriately. Rescheduling occurs when we restart
`the scheduling process from scratch. Schedule re-
`pair refers to some local adjustment of the current
`schedule and may be preferable for many reasons,
`not least because feasible schedules may be difficult
`to generate within acceptable time limits in many
`environments. The practical
`importance of the
`decision whether to reschedule or repair has been
`noted in recent papers by Lee et al. (1996) and
`Dorn and Kerr (1994). In order to decide what
`action we should take in response to an event, we
`should have some idea of the value of modifying
`our current schedules in response to the event and
`some measure of the overall impact of making
`schedule changes. In the following section we will
`use the quantitative measures of utility and sta-
`bility to assess the value and impact of schedule
`changes.
`Schedule repair plays an important role in some
`knowledge-based systems which have been devel-
`oped in the Artificial Intelligence community. ISIS
`(Fox and Smith, 1984), OPIS (Smith et al., 1990)
`and IOSS (Park et al., 1996) are systems which
`have used knowledge-based scheduling methods to
`generate a feasible
`schedule and interactive
`scheduling methods to revise the existing schedule.
`CABINS (Miyashita, 1995)
`is an intelligent
`scheduling system which integrates case-based
`reasoning mechanisms for incremental accumula-
`tion and re-use of past schedule repair experiences
`to achieve efficiency of the revision process while
`preserving the quality of the resulting schedule.
`Suresh and Chaudhari (1993) survey several other
`knowledge based systems in this area.
`Some work on schedule repair based on heu-
`ristic rules shows that schedule repair has the po-
`tential to improve the efficiency and flexibility of
`scheduling systems. Zweben et al. (1994) use sim-
`ulated annealing and constraint propagation to
`repair schedules for space shuttle ground opera-
`tions. Efstathiou (1996) introduced a software
`package, developed at Rover, to help schedulers
`carry out manual or semi-automatic schedule re-
`pair in response to real time events.
`Work on dynamic scheduling is surveyed in the
`paper of Suresh and Chaudhari (1993) and, more
`recently, in the thesis of Guo (1999). When ma-
`chine failure requires rescheduling within a job
`
`Applied Materials, Inc. Ex. 1018
`Applied v. Ocean, IPR Patent No. 6,968,248
`Page 3 of 15
`
`

`

`P. Cowling, M. Johansson / European Journal of Operational Research 139 (2002) 230–244
`
`233
`
`shop or flow shop environment we may use the
`match-up scheduling approach, which has been
`considered in several papers including Akturk and
`Gorgolu (1999) and Bean et al. (1991). When
`machine failure requires revision of the current
`schedule, this revision is carried out subject to
`ensuring that the revised schedule ‘‘matches up’’ to
`the original schedule as soon as possible after the
`machine breakdown, allowing some consideration
`of the stability of the shop. Jain and Elmaraghy
`(1997) used genetic algorithms to obtain an initial
`schedule and then heuristic rules to handle shop
`floor disruption. Daniels and Kouvelis (1995) and
`Leon et al. (1994) discussed the concept of sched-
`ule ‘‘robustness’’. Here we consider how adverse
`the effects of our chosen schedule repair strategy
`may be in response to machine failure in order to
`design a robust initial schedule to minimise these
`effects. None of the above work deals with the
`trade off between schedule quality and schedule
`stability in choosing an appropriate schedule re-
`pair strategy. Wu et al. (1993) consider this trade
`off for events taking place in real time, in order to
`compare the performance of three schedule repair
`strategies. All these approaches consider the best
`way of dealing with events as they occur, rather
`than the arrival of real time information concern-
`ing anticipated future events, where the time of
`arrival of the information is critical to the way in
`which the information may be effectively handled.
`Ehlers and Van Rensburg (1994) consider eight
`different types of real time information. Such a
`taxonomy may be useful but we consider that there
`are essentially two kinds of real time information,
`illustrated in Fig. 1: that relating to the status of
`resources and that relating to the status of jobs.
`
`Fig. 1. Classification of real time information.
`
`Real time information relating to the status of
`resources includes information concerning ma-
`chines, raw materials, tools, labour, etc. Real time
`information relating to the status of jobs includes
`tracking data for each operation, data concerning
`successfully completed processing stages and in-
`formation about schedule adherence. Information
`on actual or potential disruptions may relate to
`resources or jobs. Machine breakdowns, material
`or tool shortages and longer-than-expected pro-
`cessing times give resource problems. Job related
`disturbances arising from planning systems and
`customers include changes in priority, reassign-
`ments of jobs to orders and the emergence of new
`jobs. Quality problems may relate to both re-
`sources and jobs.
`By having well-defined procedures for handling
`real time data we may both reduce the nervousness
`of
`the system and opportunistically improve
`schedule performance, compared with using ad
`hoc approaches. Most particularly, we can make a
`priori decisions as to what levels of system dis-
`ruption are tolerable for a given level of perfor-
`mance improvement. When real time data arrives
`it is put through a four stage process: detection,
`classification,
`identification and diagnosis. Since
`real time events may occur every few minutes in a
`system (Stoop and Wiers, 1996) it is important
`that the procedure is standardised, with automatic
`computer intervention where possible. Detection:
`real time data are detected by, for example, sen-
`sors, barcode scanners or operators. Understand-
`ing the detection process will lead to effective use
`of real time data capture devices, and removal of
`unnecessary and useless devices. Classification: we
`must classify the event and decide whether it may
`be handled automatically, or requires a human
`decision-maker. Identification: after the real time
`information has been classified and possibly dealt
`with automatically, there will often remain a need
`for a more detailed analysis of the disturbance
`type. For example, we may wish more information
`as to why a machine breakdown has occurred, e.g.
`lack of maintenance or sabotage. Frequently oc-
`curring types of disturbance need deeper investi-
`gation, both for prevention and improved
`prediction. Diagnosis: here we decide what action
`to take in response to the piece of real time
`
`Applied Materials, Inc. Ex. 1018
`Applied v. Ocean, IPR Patent No. 6,968,248
`Page 4 of 15
`
`

`

`234
`
`P. Cowling, M. Johansson / European Journal of Operational Research 139 (2002) 230–244
`
`information. It is possible that we should take no
`action, conduct a limited repair or reschedule from
`scratch. We will use the quantitative measures of
`utility and stability to help us make this decision as
`to what action should be taken.
`
`3. Measures of utility and stability
`
`If we have a range of good techniques for re-
`pairing schedules and rescheduling in the presence
`of real time information, we must still address the
`important issue of whether to repair or reschedule
`and which schedule repair or rescheduling strat-
`egy should be used in response to any given
`collection of real time information. When we re-
`ceive information concerning a highly significant
`anticipated future event, such as unplanned ma-
`chine maintenance, the most appropriate course
`of action may well be to discard the current
`schedule and reschedule from scratch. In doing
`so, however, we must take into account the im-
`pact
`that
`this decision will have on current
`schedules for upstream and downstream processes
`and on future plans and schedules. When infor-
`mation concerning less significant anticipated fu-
`ture
`events
`is
`received,
`it may be most
`appropriate to adopt a schedule repair strategy,
`which attempts to find a revised schedule while
`minimising the disturbance to current and future
`plans. This ‘‘wait and see’’ approach means that
`we may do nothing or carry out only a small
`local repair in response to events. Of course we
`find, at some stage, that the accumulation of
`small anticipated events mean that the disruption
`caused by rescheduling is justified. It is important
`to note that in any operation where there are
`schedules which may be subject to unforeseen
`change, there must necessarily be a strategy for
`dealing with these events. Our experience of the
`steel, furniture and paper industries suggests that
`the strategies which are used in industry are,
`however, often ad hoc and not subject to the
`same kind of analytical rigour or sophisticated
`techniques which are applied to the scheduling
`decisions themselves.
`The practical importance of the decision whe-
`ther to do as little as possible, locally repair the
`
`schedule or to reschedule from scratch in response
`to a real time event is identified in Lee et al. (1996)
`and Dorn and Kerr (1994). Both these papers
`discuss decision support for scheduling of primary
`steel making processes, where a great deal of real
`time process control information is available.
`In this section we will define two measures to
`guide the decision as to what strategy should be
`used to repair a schedule in response to real time
`information, utility and stability.
`Utility will measure the benefit which may be
`gained by using a particular rescheduling strategy.
`Suppose that we have a mathematical model M of a
`scheduling process, where we have n numerically
`defined objective criteria ðO1; O2; . . .; OnÞ. Without
`loss of generality we suppose that each objective
`criterion is to be maximised. For example a piece
`of real
`time information arising from process
`control computer might be that upstream process
`controllers report that ‘‘the true size of job A123
`is 50% greater than the scheduled size’’. Clearly
`the value of this information for rescheduling
`purposes depends heavily on the time at which it
`arrives. We suppose that
`for a (potentially
`time information E
`compound) piece of real
`there is a strategy S0, corresponding to the no-
`tion of
`‘‘do nothing’’, which yields objective
`function values ða1; a2; . . .; anÞ. For example S0
`might correspond to the strategy ‘‘make the
`originally scheduled orders to stock in response
`to the customer order cancellation in the hope of
`a later sale’’ or ‘‘create a buffer of work to be
`done in front of the malfunctioning machine and
`leave other machine schedules unchanged’’, with
`this latter strategy corresponding to the pushback
`strategy of Bean et al. (1991). A further example
`is given in the following section. Suppose further
`that we have a strategy S1 which will produce a
`unique
`solution for
`the
`scheduling problem
`modified by this real time information, yielding
`ðb1; b2; . . .; bnÞ. Then
`objective function values
`the utility U is the multiple valued function gi-
`ven by
`UðM; S0; S1; EÞ ¼ ðb1 a1; b2 a2; . . .; bn anÞ:
`When the model M has only a single objective
`criterion we will have a strategy Sopt which will
`give an optimal solution in response to the real
`
`Applied Materials, Inc. Ex. 1018
`Applied v. Ocean, IPR Patent No. 6,968,248
`Page 5 of 15
`
`

`

`P. Cowling, M. Johansson / European Journal of Operational Research 139 (2002) 230–244
`
`235
`
`strategy Sstatic gives us a schedule where the start
`times are t1; t2; . . .; tn and the completion times are
`C1; C2; . . .; Cn, respectively. Suppose that in re-
`sponse to the set of real time events E we apply
`scheduling strategy Sreact and the revised schedule
`
`
`has new start times t01; t02; . . .; t0
`n and new comple-
`
`
`tion times C01; C02; . . .; C0
`n, respectively. For real
`time information E arriving at time t we define
`the stability SðM; Sstatic; Sreact; E; t)
`to be some
`function of the start and completion times before
`and after rescheduling. Our stability measure
`cannot be obtained directly from our scheduling
`model in the same way that utility was obtained
`from the objective criteria. However,
`it seems
`sensible to require that the stability function is
`
`
`non-decreasing with each of jti t0ij and jCi C0ij.
`A simple example of a stability function might
`then be
`SðM; Sstatic; Sreact; E; tÞ
`¼
`
`
`
`
`minfaðjti t0ij þ jCi C0ijÞ; Dig;
`
`Xn
`
`i¼1
`
`where Di represents the maximum possible dis-
`turbance which might occur due to movement of
`the job Ji (e.g. the cost of outsourcing the job) and
`a is a parameter which represents the ‘‘cost’’ of
`the destabilising effect per time unit which the job
`is moved. We will explore the properties of a
`slightly different stability measure in the following
`section.
`Given measures for the utility and stability of
`a strategy for the use of real time information in
`scheduling decision making we may trade off the
`desirable effects of high utility with the undesir-
`able effects of a large impact on the stability. In
`Section 4 we will consider how this might be
`done in one particular case. The use of utility
`and stability measures as described in this sec-
`tion gives us a basis upon which to analyse a
`given planning and scheduling environment and
`arrive at concrete recommendations to choose
`between strategies for dealing with real time in-
`formation. We should be able to choose among
`a range of strategies, which are not dominated
`in terms of
`their stability and utility perfor-
`mance, for dealing with real time information
`effectively.
`
`time information E arriving at time t. If there is a
`clearly defined ‘‘do nothing’’ strategy S0 then for
`time events E we may
`any given set of real
`simply say that the utility of the real time in-
`formation concerning real time events E, arriving
`at time t, UðM; E; tÞ ¼ vopt v0, where vopt is the
`objective value given by strategy Sopt and v0 is the
`objective value given by strategy S0. By deriving
`such a function for utility, we may make minor
`changes to many scheduling models in order to
`evaluate the benefit which may be gained from
`the use of real
`time information within that
`model.
`To further increase the usefulness of our utility
`measure, we must also consider the disbenefits
`which occur due to disruption of the planned
`production processes for dynamic schedules at
`different planning horizons or for upstream and
`downstream processes. In the matchup scheduling
`approach discussed earlier (see for example Ak-
`turk and Gorgolu, 1999) we measure the disrup-
`tion of schedule repair due to machine failure as
`the time until the repaired schedule matches up
`again with the planned schedule. Here we propose
`a more general approach. The problems associ-
`ated with changing a scheduling decision may be
`very complex. Any model built
`to support
`scheduling decisions is unlikely to be able to take
`all of the possible factors into account and it may
`be appropriate to model the effect on stability in
`some simplified way. To accurately model the
`stability effects of a given local schedule change
`we would need to solve a global resource alloca-
`tion, planning and scheduling problem across all
`upstream and downstream processes and within a
`time horizon of those schedules which are affected
`by the local change. Since this is unlikely to be
`practically possible we suggest here some simple
`stability measures based upon the
`temporal
`movement of tasks, using the idea that the most
`significant effects of the movement of jobs is in
`changing release dates for upstream and down-
`stream processes. Our measure is related to that
`of Wu et al. (1993) which incorporates starting
`time movements and a measure of the change in
`job sequence. Suppose that in our model M we
`have jobs J1; J2; . . .; Jn
`to schedule through a
`subset of the production process, and that some
`
`Applied Materials, Inc. Ex. 1018
`Applied v. Ocean, IPR Patent No. 6,968,248
`Page 6 of 15
`
`

`

`236
`
`P. Cowling, M. Johansson / European Journal of Operational Research 139 (2002) 230–244
`
`4. Stability and utility of a single event for n=1==C
`
`In order to illustrate our notions of utility and
`stability, we will investigate these measures for the
`n=1==C scheduling model, where n jobs J1; J2; . . .;
`Jn having processing times p1 6 p2 6 6 pn, are
`to be scheduled on a single machine in order to
`minimise the average completion time and pre-
`emption is not allowed. The optimal sequence S0,
`P
`given by the shortest processing time (SPT) rule,
`is ðJ1; J2; . . .; JnÞ. In this optimal sequence job Ji
`will have completion time Ci given by Ci ¼
`¼1 pi ði ¼ 1; 2; . . .; nÞ and the average comple-
`tion time C is given by
`C ¼ 1
`Ci ¼ 1
`ðn i þ 1Þpi:
`n
`n
`
`Xn
`
`i¼1
`
`ij
`
`Xn
`
`i¼1
`
`Consider the real time event E ‘‘the processing
`time for job Jk changes from pk to p0
`k’’. The time t
`at which this information arrives may be before,
`during or after the processing of job Jk
`in the
`original schedule. We will derive expressions for
`the utility of this piece of real time information
`and the effect on stability of adopting a strategy
`which maximises utility without
`considering
`stability.
`In Fig. 2 we illustrate the three separate cases
`where job Jk will be moved in response to real
`time data E arriving at time t. In (i) we see that
`the processing time for Jk has become shorter and
`the revised processing time information has ar-
`rived in time so that job Jk may be placed in the
`sequence at the position suggested by the SPT rule
`to produce a new sequence to optimise utility. In
`(ii) we see that the processing time for Jk has be-
`come shorter, but this time the revised processing
`time information has arrived too late for job Jk
`may be placed in the sequence at the position
`suggested by the SPT rule, so job Jk must simply
`be placed as soon as possible after time t to make
`optimal use of the real time information with re-
`spect to utility. In (iii) we see that the processing
`time for job Jk has increased and information
`about the revised processing time has arrived in
`time to revise the schedule in accordance with the
`SPT rule.
`Let the set of jobs which are moved in the
`final sequence, apart from Jk, be denoted D. Let
`a be the number of jobs coming after all the jobs
`whose position in the sequence has changed,
`then
`
`0;
`n k;
`jfi : pi > p0
`kgj;
`
`k ¼ n;
`6 pkþ1;
`k < n; p0
`k
`k < n; p0
`k > pkþ1:
`
`8><
`>:
`
`a ¼
`
`Xn
`
`i¼1
`
`Suppose that we receive real time information
`concerning an event E at time t and in response to
`this information we create a new schedule S0 in
`which job Ji has processing time p0
`i and completion
`time C0
`i, where the job sequence and completion
`times may or may not be changed by the event and
`the strategy for dealing with it.
`Define the utility, UðS0; S0; E; tÞ, of information,
`arriving at time t, concerning real time event E as
`the difference in the objective C between a strategy
`S0 which ignores the real time event E, thus staying
`with the scheduled sequence, and strategy S0 which
`uses it. When S0 makes optimal use of the infor-
`mation given the nature of the anticipated future
`event and the time t at which it arrives, we may
`simply write UðE; tÞ in the notation of the previous
`section.
`The stability measure we shall consider for the
`n=1==C model is the sum over all jobs of the ab-
`solute change of start and finish times divided by
`the number of jobs. Hence our measure of the
`impact of moving from schedule S0 to schedule
`S0; SðS0; S0; E; tÞ is given by
`SðS0; S0; E; tÞ
`
`¼ 1
`n
`
`
`
`ðjCi C0ij þ jðCi piÞ ðC0i p0iÞjÞ:
`
`
`
`In writing our expressions for U and S above we
`have omitted the model identifier M since we are
`referring throughout to the n=1==C model.
`
`Fig. 2. Movements of job Jk for different values of p0
`k and t.
`
`Applied Materials, Inc. Ex. 1018
`Applied v. Ocean, IPR Patent No. 6,968,248
`Page 7 of 15
`
`

`

`P. Cowling, M. Johansson / European Journal of Operational Research 139 (2002) 230–244
`
`237
`
`P
`decreased by pk, while job Jk will have its start time
`fi:Ji2Dg pi and its finish time in-
`increased by
`
`creased by jpk p0kj þ
`fi:Ji2Dg pi. Jobs Jiþ1; Jiþ2;
`. . . ; Jn will have their start and finish times in-
`
`creased by jpk p0kj.
`To investigate the behaviour of utility and sta-
`bility, we simulate a 20 job problem with pro-
`cessing times uniformly distributed on the interval
`½0; 10Š. At time t, we receive the real time infor-
`mation that the processing time for J10, originally
`5.53 changes to p0
`10. We will explore the behaviour
`of utility and stability for different values of p0
`10
`and t. In Fig. 3 we graph utility against p0
`10 and t
`assuming that we reschedule to optimise utility. In
`Fig. 4 we graph stability against p0
`10 and t, both for
`the case where we reschedule so as to optimise
`utility and in the case where we do not change the
`job sequence.
`We can see that when p10 undergoes a small
`change then the utility of the information and the
`effects of rescheduling are both small. When p10
`undergoes a larger change then the utility of the
`information is much higher as is the change in
`schedule stability caused by acting upon the in-
`formation. When the processing time for job J10 is
`reduced, then the utility of the information ex-
`hibits a nearly linear dependence on the new pro-
`cessing time, increasing with the time of arrival of
`the information. When the processing time for job
`J10 is increased, the utility’s dependence on the
`time is only insofar as the utility will be zero when
`the information arrives too late. The important
`point to note from the two graphs is that the utility
`
`P
`
`Fig. 3. Utility for different values of p0
`10 and t.
`
`Define p0 ¼ 0, pnþ1 ¼ 1 for notational conve-
`nience. Then we have
`fJi; Jiþ1; . . .; Jk1g
`t 6 Ci1; pi1 6 p0
`k < pi < pk;
`fJi; Jiþ1; . . .; Jk1g
`i > 1; Ci2 < t 6 Ci1; p0
`k < pi < pk;
`fJkþ1; Jkþ2; . . .; Jig
`6 piþ1;
`t 6 Ck1; pkþ1 < p0
`; otherwise;
`and we have
`UðS0; S0; E; tÞ ¼ Uððp1; p2; . . .; pnÞ; k; p0
`k; tÞ
`¼ 1
` p0
`n
`
`ð2a
`
`k
`
`

`
`k
`
`

`
`

`
` p0
`
`k
`
`!
`
`pi
`
`

`
`Xn
`
`fi:Ji2Dg
`
`8>>>>>>>>><
`>>>>>>>>>:
`
`D ¼
`
`and
`
`SðS0; S0; E; tÞ ¼ 1
`n
`
`þ 1Þ pk
`
`Xn
`
`þ 2
`
`fi:Ji2Dg
`
`
`
`ðpi þ minðpk; p0kÞÞ
`
`:
`
`The expression for utility arises by considering the
`difference in completion times between the original
`sequence, using a ‘‘do nothing’’ strategy in re-
`sponse to the new processing time p0
`k for job Jk,
`and the sequence following the movement of job Jk
`by strategy S0. If job Jk moves earlier in the se-
`P
`quence, then the jobs in D will have their com-
`pletion times increased by p0
`k, while job Jk will have
`fi:Ji2Dg pi. If job Jk
`its completion decreased by
`P
`moves later in the sequence, then the jobs in D will
`have their completion times decreased by p0
`k, while
`job Jk will have its co