NASA Technical Memorandum 102367

Application of a Hybrid Generation/Utility

Assessment Heuristic to a Class

of Scheduling Problems

(NASA-TM-]O_367) APPLICATIC)N OF A HYBRID

GEN_RATTON/UTrLrTY ASSESSMENT H_URISTIC TO A

CLASS OF SCNEr_ULiNG PRORL_MS (NASA) I__ p

(.SCL IZB

N90-I0674

Uncl_s

G3/66 0234693

Ann O. Heyward

Lewis Research Center

Cleveland, Ohio

Prepared for the

International Conference on Systems, Man, and Cybernetics

sponsored by the Institute of Electrical and Electronics Engineers

Cambridge, Massachusetts, November 14-17, 1989

APPLICATION OF A HYBRID GENERATION/UTILITY ASSESSMENT HEURISTIC TO A CLASS OF SCHEDULING PROBLEMS

Ann O. Heyward

NASA Lewis Research Center

Cleveland, Ohio

_o

LO

ABSTRACT

A two-stage heurlstlc solution approach for a

class of multlobjectlve, n-job, l-machine schedulIng problems Is described. Minlmlzatlon of "jobto-job" interference for n jobs is sought. The

first stage generates alternative schedule sequences by interchanging pairs of schedule elements.

The set of alternative sequences can represent

nodes of a decision tree; each node Is reached via

decision to interchange job elements. The second

stage selects the parent node for the next generation of alternative sequences through automated

paired comparison of objectlve performance for all

current nodes. An appllcatlon of the heuristic to

communications satellite systems planning Is

presented.

1. INTRODUCTION

ThlS paper discusses an heuristic approach to

solving a class of problems that may be formulated

as muitiobJectlve, n-Job, I-machlne schedullng

problems. The problem has n objectives: the

minimization of "Job-to-Job" interference experienced by n Jobs to be scheduled consecutively on

one machine. Job-to-Job Interference may represent

a variety of factors which Impede scheduling of

jobs In immediately adjacent tlme slots, In a manufacturlng environment, such a factor might be the

need to remove fillngs from a work surface between

the machining of parts. As noted by Ignlzlo [4],

electromagnetlc interference between communications signals may also be modeled as Job-to-job

interference, as In the application presented here.

Improvement of an existlng schedule Is sought, as

opposed to absolute optlmallty: therefore, an heurlstlc approach Is sultable. A two-stage heurlstic

procedure Is descrlbed. The first stage generates

alternative schedule sequences vla an heuristic

swapping procedure, which Interchanges pairs of

schedule elements (jobs). The set of alternatlve

arrangements that may be derlved from an existing

arrangement can represent nodes of a declslon

tree; thus, each node Is reachable vla a decision

to interchange two job elements In the exlstlng

arrangement. The first stage of the heurlstlc

enumerates all decision tree nodes reachable from

the current arrangement. The second stage of the

heuristic selects the most promising potential parent node from those enumerated by the f_rst stage,

through automated paired comparison of all current

level nodes, for the next generation of alternative

schedules.

An extensive body of literature exists for

scheduling problems In general (e.g., see Graves'

survey [3]) and for n-Job, l-machine scheduling/

sequencing problems In particular. Proposed so!utlon techniques have included goal programming [4]

and dynamic programming Ill] as well as more traditlonal methods applied to alternative problem

formulations [a]. Strategies for reducing the

solution space of possible sequences and schedules,

or improving efflciency of search algorlthms vla

the exploitation of precedence constraints and/or

dominance concepts appear In Ill, [2], [5], [9],

and Ill]. Extensive work has been performed on the

use of Interactlve palred comparlson of alternative

options to obtaln information about preference

relationships, as described In [6]. The approach

presented In thls paper explolts precedence constraints, a particular domlnance concept, and automated paired comparison. The technique can thus

be said to represent a hybridlzation of solution

generation and utillty assessment techniques -

approaches that are generally utillzed Independently of one another.

The heuristlc described has been implemented

wlthln a module of a computer software package

deslgned for communIcatlons satellite systems plannlng: the Numerical Arc Segmentation Algorithm for

a Radio Conference (NASARC) [12,13].

Orlglnally developed at NASA/Lewls Research

Center as a plannlng tool for the 1988 Space World

Administratlve Radlo Conference, the package Is

deslgned to develop orbital arc segments that are

shared by groups of satellites. In general, satellites allotted to different arc segments will pose

a potentially harmful level of Interference to one

another; thus, the proximity of their respective

arc segments will affect the level of Interference

experienced by satellites wlthln each segment. An

exact parallel exists between the problem of developlng an arrangement of orbital arc segments that

mlnlmlzes such segment-to-segment interference, and

the n-Job, 1-machlne scheduling problem where the

goal is to mlnlmlze the level of Job-to-job Interference experienced by all Jobs.
2. REPRESENTATION OF THE SCHEDULING

PROBLEM AS A DECISION TREE

Prior to discussion of the heurlstlc In more

detail, It is appropriate to lay the groundwork

for the algorithm by representing the n-job,

l-machlne scheduling problem as a decision tree

search problem.

The scheduling problem addressed here may be

stated in general terms, as follows: given n

jobs to be scheduled on one machine, determine the

best schedule with respect to one or more optimalIty criteria, subject to constraints imposed upon

the tlme slots available to each Job. If we may

treat schedules as sequences, a direct (though not

one-to-one) mapping of the set of all possible

solutions to a declslon tree exists.

Wlthout loss of generality, It Is assumed that

some Initial sequence exists. This initial orderIng of Jobs may be regarded as the single "parent"

node for a declslon tree. Each direct descendant

of the Initial parent sequence will be reached by a

single two-Job permutation, or Interchange, In the

order In which Jobs are to be performed - similar

to that described by Emmons [1], Picard et al. [8],

or Reiter eta]. [9]. Thus, If our initial schedule Is represented by an ordering (l, 2 ..... n),

the next generation will consist of [_] possible

schedules. If each node In thls generatlon were

to be treated as a potential parent node the following (second) generation would contaln posslble orderings. In general, the kth generation

will contaln nodes, each of which represents

a posslble schedule. It Is clear that no loss of

genera]ity Is experlenced In the assumption of an

initial orderlng; eventually all (n!) posslble

schedules will each be represented by one or more

nodes In the decision tree. This concept is illustrated In Fig. I.

The three-Job example presented In Flg. 1

illustrates some potential drawbacks of thls representatlon of the scheduling problem. Schedules

may be duplicated at several nodes, and the declslon tree will grow explosively as the number of

Jobs Increases. However, the issue of feasibility

has not yet been dealt wlth. It Is expected that

some interchanges of Jobs withln the schedule will

be prohibited by virtue of tlme constraints that

restrict when these Jobs may be performed, i.e.,

precedence constraints. In fact, some Jobs may be

effectlvely fixed wlthln the schedule If their feasible times are sufficiently restricted. The number of feasible schedules of n Jobs for a given

problem may thus be significantly less than in!),

as noted by Emmons [l], Erschler et al. [2], and

Pasch [7]. Interchanges that are infeasible need

not be represented within the decision tree, which

wlll reduce both the total number of nodes and the

number of nodes representlng duplicate schedules.

The slze of the decision tree Is also Influenced by efflclent enumeration of decision tree

nodes. Enumerating only those nodes meeting an

efficiency criterlon wlll effect further reductlons

of decision tree size. Efgicient enumeratlon of

decision tree nodes Is addressed In two ways by the

heuristlc. First, In any new generation of nodes,

only those nodes that represent schedules that

Improve upon (i.e., domlnate) the schedule of the

parent node are enumerated (Stage I). Second, enumeration of the next generation of nodes starts

From the single most promising (most dominant) parent node of the current generation (Stage II).

The use of dominance concepts in improving

efficiency of enumeration Is also addressed in

Emmons [I], Erschler et al. [2], and Picard

et al. [8].

3. HEURISTIC STAGE I: ENUMERATION OF

DECISION TREE NODES

We wish to enumerate only those nodes that

satisfy criteria For both feasibility and efficiency. Stage I of the heurlstic accomplishes this

purpose by comparing projected objective function

performance of potential new nodes with the objective function values of the parent node. New nodes

which dominate the parent node are generated; nodes

which do not are discarded. Only nodes which are

the product of feaslble interchanges are assessed.

Prior to defining feasibility and efficiency

conditions, it is appropriate to present a generalIzed formulatlon of the scheduling problem we wish

to address:

Minimize Zk =

n n

I: I: x1j(xj ,k_l+Xj ,k+l)Ci j

i=I j-1

k=l, ..., n

Subject to:

TIt _ t11, i=I ..... n

t21 ! T21, I=I .... , n

t21 - tli = ri, I:I, ..., n

(3.1)

(3.2)

(3,3)

(3.4)

n

I: Xlk=l, k.1 ..... n

I-I

(3.5)

XjmXlK(tlJ-t2j) Z O, i=I ..... n

j:1 ..... n, J_I

k:1 .... , n

m:k+I, ..., n (3.6)

where

Xlk - {0,I}, I=I ..... n

k=1 ..... n (3.7)

t21, tll Z O, I=1 ..... n (3.8)

Tll

T2t

Indlces of Jobs referenced to positlons In

Inltlal (parent) sequence

measure of job-to-job interference experienced by Job I as a result of adjacency

to job J In the scheduled order of Jobs

(constant for each pair i,j)

earllest feasible tlme at which job i may

be begun (constant)

latest feasible tlme at which Job I may

be completed (constant)

2
tll start time, job i

t21 completion time, job I

r i requlred length of tlme to perform job

(constant)

X_k {l if job I

of jobs}

{0 otherwise}

is kth In the scheduled order

The set of n obJectlves (3.1) consists of

minimlzation of the degree of job-to-job interference experienced by each job. Constraints (3.2) and

(3.3) ensure that the time slots found for all jobs

i Fall within the time limits feasible for each

job. Constraint set (3.4) ensures that the time

slot scheduled for each Job I is of exactly the

requlred length. Constraint set (3.5) ensures that

exactly one Job i is assigned to each position in

the scheduled ordering of jobs. Constraints (3.6)

enforce non-overlap of tlme Intervals allotted for

jobs 1 to n. Constraints (3.7) enforce integralIty of the Xik, and constraints (3.8) enforce

nonnegativity.

We define feasibility conditions For the

interchange of two Jobs within an existing sequence

in terms of the problem just presented. An interchange of jobs i and J Is feasible If and only

if the following three condltlons are met:

mln(T2i,T2j ) - max(Tli,TlJ ) Z ri + rj (3.9)

max(t2i,t2j) _ mln(T2i,T2j) (3.10)

min(tll,tlj ) Z max(Tli,TlJ ) (3.11)

Conditlon (3.9) guarantees that the intersection of the allowable tlme Intervals for performance of Jobs i and J is of at least the length

of tlme required to complete both jobs. Conditions

(3.10) and (3.11) ensure that the intersection of

the feasible tlme intervals for Jobs 1 and j

encompasses both of the time intervals allotted to

jobs I and J. Note that a slightly dlfferent

interpretation may be given to the variables tli,

t21, tlj, and t2_: the values of these varlables

define the current time Intervals allotted to Jobs

i and J. Thus, compllance with conditions (3.10)

and (3.11) implies that the current tlme slots for

Jobs i and J may be Interchanged In order and

still remain withln feaslble limits in both cases.

Condltlons (3.9) to (3.11) are illustrated In

Fig. 2.

Conditions (3.9) to (3.11) may be applied to

all palrs of Jobs I and j to construct a matrix

of feasible Interchanges. The matrix will be

square, but nonsymmetrlc. Each column corresponds

to a Job I, and contains the jobs J which may

be interchanged with Job I. Matrix entries are

defined as follows:

aj ,i {j If job j

job i}

{0 otherwise}

is interchangeable with

By examining the matrix, we can restrict enumeration of nodes to those that are the product of

feasible interchanges.

In examining the problem defined by (3.1) to

(3.8), we observe that any feasible solution will

have a corresponding objective vector containing

n elements. Our definition of efficiency will be

based upon element-by-element comparison of objective vectors, but first it Is appropriate to more

clearly define the objectives to be calculated.

Measures of various types of interference

between two elements may be expressed !n terms of

the separation between the two elements required

to reduce the level of Interference _o an acceptable level or to eliminate it completely. A measure of thls type Is often preferable to a rigorous

computation of Interference, as expressions For

interference are often nonlinear. If done on a

worst-case basls, measures of this type have the

addltlonal advantage of requlrlng a one-time a

priori calculation, rather than continual reevaluation of a complicated expression.

Me will assume that we have available (or can

readily calculate) a matrix of required minimal

tlme separations between all palrs of jobs i and

j, calculated on the assumption that jobs 1 and

J are adjacent In the scheduled order of Jobs.

The required tlme separation will thus be worstcase. The elements of this matrlx will provide the

alj of (3.1'), l.e., ali will be the time requlred

between finishing Job T and starting job J if

jobs 1 and J occupy adjacent positions in the

scheduled order.

The efficiency of an Interchange Is evaluated

by calculatlng the resulting change in affected

objectlve function values. For a given interchange

of two jobs i and J, in sequence positlons k

and m, up to six objective function values may be

affected, namely, those objective values for jobs

asslgned to positions k-l, k,k+l, m-l, m, and m+l

(see Fig. 3). Assuming that the goal Is to improve

the obJectlve value for position k, the new objective value obtained when job 1 Is interchanged

wlth job J Is calculated first. If the objective

value Is degraded, the interchange Is rejected. If

the objective value is improved, the magnitude of

the improvement Is calculated to be used as a standard of reference. Remaining affected obJectlve

values are calculated. If any value is degraded as

a result of the interchanges of jobs 1 and J,

the degradation must be of lower magnitude than

the degree of Improvement galned In objective i.

If this crlterlon is not met, the interchange Is

rejected.

If the interchange is efficient, generation of

a new node (sequence) is attempted. If the length

of time required for Jobs in sequence positions k

and m are equal, a direct swap of thelr slots In

the sequence may take place. It is possible, if

the jobs requlre different lengths of time, that

one avallable time slot will be of Insufficlent

length to allow direct Insertlon of a longer Job.

In this case, a simple algorithm may be applied to

laterally shlft adjacent jobs to slightly later or

earlier tlme slots to open a time slot of sufficient

length. Thls process is illustrated in Fig. 4.
If a tlme slot of sufficient length cannot be

created for the longer job, the Interchange is

rejected. If the longer Job can be scheduled, the

new sequence Is generated and stored for comparison with other nodes of the current generation.

The heuristic will then evaluate the next feasible

interchange for job I, applying the same efficiency tests.

Assuming a priori generation of feaslble

Interchange and interference measure matrices,

Stage I of the heuristic may be descrlbed as

follows:

Step I:

Step 2 :

Step 3:

Step 4:

Step 5:

Step 6:

Step 7:

Determine next candidate Job to be utillzed for node generation (job i). If

candidates are exhausted, stop.

By examining column i of the feasible

Interchange matrix, select next candidate Job j for possible interchange

with Job I. If candidates are

exhausted, go to Step I.

Calculate objective value for kth slot

resulting from substltutlon of job J

for Job i. If objective value Is

degraded, update Interchange matrix and

go to Step 2. Otherwise, calculate

Improvement gained.

Calculate objective value for slots k-l,

k+l, m-l, m, and m+l. If, for any objective value, degradation Is not offset by

improvement In objective value for kth

slot (Step 3), update Interchange matrix

and go to Step 2.

If required times for performance of Jobs

I and J are equal, interchange time

slots and generate new ordering. Update

Interchange matrix and go to Step 2. If

times are unequal, go to Step 6.

Calculate tlme available between Jobs

occupying slots adjacent to shorter Job.

If time available is of sufficient length

for longer job, allocate tlme slots and

generate new ordering. Update Interchange matrix and go to Step 2. If tlme

available is Insufflcient, go to Step 7.

Attempt lateral shift of Jobs adjacent

to desired tlme slot to earlier/later

startlng tlme to open slot of sufflclent

length. If lateral shift fails, update

interchange matrix and go to Step 2. If

lateral shift succeeds, allocate tlme

slots and generate new ordering. Update

Interchange matrix and go to Step 2.

A further efflclency enhancement may be realIzed through generatlon of an efficient Initial

parent node for the decision tree. This Is accomplished via application of Stage i. The matrix of

feasible interchanges may indicate that selected

pairs of schedule elements are interchangable only

wlth each other; such elements are termed "pairrestricted". An Important feature of such interchanges Is that their execution can affect no

other outcome of Interchanges. Thus, if a palrrestricted Interchange Improves the Initial schedule supplied to the algorithm, a more efficient

starting sequence Is generated. Generatlon of an

efficient starting node may take place prlor to a

more general examination of the interchange matrix

for all i, as described above. However, straightforward, successive apDlications of Stage I to the

Initial schedule will also result in :he eventual

acceptance of all efficient pair-restricted

interchanges.

4. HEURISTIC STAGE II: SELECTION OF PARENT

FOR NEXT GENERATION OF NODES

While the steps taken In Stage I of the heuristic reduce the number of nodes In the sc_eduling

decislon tree by limltlng nodes to those representing only feasible and efficient sequences, it is

still possible that a given generation of nodes

will contaln a large number of members, particularly if the number of Jobs to be scheduled is

large or if there are few precedence constraints.

Thus, to further reduce the size of the scheduling

decision tree and yet still obtain a good-quality

schedule, Stage II of the heuristic selects the

dominant node of the current generation. Stage I

of the heurlstic is then applied to this node In

creating the next generation of possible sequences.

Selection of the domlnant parent node is performed through automated paired comparison of

schedules. Extensive work has been carried out by

Maiakooti [6] on the use of Interactlve paired comparison between alternatives in the assessment of

utility functions. However, automated paired comparlson is appropriate for thls problem because the

quality of one schedule versus that of another may

be readily assessed by a single quantitative utilIty measure. Preference results wlll be transitive, guaranteeing that selection of the dominant

parent node through paired comparison will not

ellmlnate a node that might have been preferable to

our flnal cholce.

Stage II of the heurlstlc is performed after

each completed application of Stage I; i.e., after

a new feasible, efficient node has been generated.

The new node will be compared with the best node

found so far, on the basis of a numeric index of

solutlon utility. If the newest node is domlnant,

the existing best node will be replaced. At the

beginnlng of each new generation of nodes, the current best node will be the dominant parent found in

the prior generatlon. At the end of each new generatlon of nodes, the current best node will be the

dominant parent for the next generation.

Solution utillty is assessed on the basls of

comparative objectlve function performance. The

objective vector of the existing best node and the

objective vector of its potential replacement are

compared on an element-by-element basis. Slnce our

goal is to reduce Job-to-Job interference in all n

time slots, a simple measure is defined for overal]

solution utility:

n

QJk- I: 6ij k j,k:l,2,j_k

i=l

where

4
S_jk {l, If the ith component of the objective Is

lower In value for solution j than the

corresponding objective component for solutlon k}

{0 otherwise}

Q12 thus provides a count of the number of

objective values that are lower for solution I (the

best solution so far) than their counterparts for

solution 2 (the new node). Q21 provides a similar

index for the new node versus the best node found

so far. The solution that Is preferred Is that for

which the maximum of Q12 and Q21 is attained,

i.e., the solution that corresponds to a _reater

number of lower objective values. It Is possible

that a tle wlll result. In that case, the solution

with the lowest average objective value over n

components Is considered dominant. In the unlikely

event that a tle results for thls preference measure, the existing best solution Is retained.

The complete heurlstlc, incorporating both

Stages I and II, may now be stated:

Step l:

Step 2:

Step 3:

Step 4:

Step 5:

Step 6:

Step 7:

Step 8:

Step 9:

Step 10:

Generate a matrix of interference measures, for all possible adjacent pairings

of Jobs.

Generate a matrix of feasible interchanges from an existing schedule, uslng

conditions (3.9) to (3.11).

Examine matrix for palr-restricted Interchanges. If none are found, continue.

If palr-restricted Interchanges exist,

apply Stage I to create efficient startIng sequence. If initial sequence cannot be improved, starting sequence Is

Initial node supplied to heuristic.

Update interchange matrix, elimlnatlng

both accepted and rejected interchanges.

If the matrix Is nonempty, continue. If

no Interchanges are feaslble, stop. Best

feasible node has been found.

Apply Stage I to create a new node

(sequence).

Compute solution utility Indices Q12

and Q21 for the best solutlon to date,

and Its potentlal replacement. If

Q12 _ Q21, go to Step 9.

Compute the average obJectlve functlon

value, over the n components of the

objective vector, for the sequences

represented by each node.

On the basis of the preference criterion,

select the dominant solution that will

become the best solution found to date,

of the current generation.

If the interchange matrlx has not yet

been examined for all Jobs I, go to

Step 5. Otherwise, the current generation Is complete; go to Step 4.

5. APPLICATION OF THE HEURISTIC WITHIN

THE NASARC SOFTWARE PACKAGE

The Numerical Arc Segmentatlon Algorithm for a

Radio Conference (NASARC) Is a software package

developed at the NASA/LewIs Research Center as a

tool for use at the 1988 World Administrative Radlo

Conference for a11otment planning of satellltes In

the expansion frequency bands of the Fixed Satellite Service. NASARC utlIizes heuristic algorithms

to produce a collection of orbital arc segments,

each shared by a group of "compatible" satellite

systems. Systems are compatible _f they exert

relatively little interference upon one another in

splte of minlmal orbital seDaration. Each group of

compatible satellites, and its associated arc segment, may be regarded as a single unlt. Each such

unit must be placed - or "scheduled" - in some portion of the 360-_egree geostationary orbital arc.

The geostationary orbital arc may be regarded

as a finite continuous interval within which a

number of arc segments of varying length must be

accommodated. Satellite systems exert a degree of

electromagnetic interference upon one another that

Is largely dependent on the proximity of thelr

respective positions In the geostationary orblt In

relation to the geographical proximity of their

service areas. Thus, systems associated with a

given segment of the orbltal arc interfere to varyIng degrees wlth systems associated with all other

segments. Segment-to-segment interference can thus

be quantified In terms of the interference between

systems associated with each segment. The arc segment placement problem is therefore directly analogous to the n-job, l-machine schedullng problem,

where the objective Is to minlmlze the Job-to-job

interference experlenced by each of the n jobs.

In order to improve the arrangement of such

segments withln the geostationary arc, the heuristic described In previous sections was implemented

in a module of the NASARC software package. The

module seeks an arrangement of arc segments that

results In minimal Interference between systems in

adjacent segments.

The degree of Interference experienced by systems within a glven arc segment (with respect to

systems In immediately adjacent segments) can be

evaluated via a requlred separation measure of the

type described in Section 3. Segment-to-segment

interference Is characterized as the normalized

orbltal separation requlred between systems In

adjacent orbltal arc segments as follows:

M N

EI (HI) - I: I; sij

i=I j_1

H*N

where:

ET or WI

slj

interference measure assoclated with

arc segment immediately adjacent to

the East (following) or West (preceding) of segment I

the number of systems in segment I

the number of systems in segment I+l

OF l-I

orbital separation requlred between

satellites i and J

The quantitles WI and EI are equivalent to

the quantities .aij as defined In Section 3, and

are determlned oy calculation prlor to application

of the heuristic. The heuristic will seek improvement In n objectives for n arc segments, i.e.,

ZI = EI + W I, I=I n
whlch are similar to the set of objectives defined

by (3.1).

An Inltlal arrangement of arc segments Is

determined prior to application of the heuristic.

The heuristic then interchanges locations of pairs

of arc segments (and their associated satellite

systems), in an attempt to decrease Interference

between systems in adjacent portions of the orbital arc.

A matrix of feasible segment interchanges Is

flrst created. An Interchange of segments is feasible if and only if the two segments meet the following conditions:

(1) The feasible arc locatlons associated with

each segment intersect by at least the sum of the

required arc lengths for each segment.

(2) The Intersectlon of the feasible arc locatlons assoclated with each segment encompass both

segments' currently a11otted arc 1ocatlons.

These conditions are those defined formally by

(3.9) to (3.11), but have an additional physical

Interpretatlon for this applicatlon. Condition (I)

restricts our conslderatlon of alternatives to

meanlngful alternatives. If condltion (I) Is not

met, the two segments are restrlcted to portions of

the orbit that are sufficiently distant to Imply

that the appropriate service areas cannot be served

by appropriate sate111tes If the locations of the

segments are Interchanged. Condition (2) ensures

that we may directly Interchange segments In our

arrangement, subject to minor adjustments for

sllghtly different length requirements for the two

segments.

The process described in Sections 3 and 4 Is

then applied to the arc segment arrangement problem. The matrix of feasible Interchanges Is examined for palr-restrlcted interchanges. Those

resulting in an improved arrangement are carried

out, and an efficlent startlng solutlon is generated. Examlnatlon of the updated Interchange

matrix then begins and new arrangements are generated (Stage I) and evaluated vla paired comparlson

(Stage II). Finally, when no further Interchanges

are possible, the improved arrangement Is output

as the final arrangement of arc segments derived by

the NASARC software package.

A short computatlonal example illustrates the

use of the algorithm within the NASARC software.

The NASARC package consists of four program modules with the above algorithm resldlng within the

fourth and final module. For the purpose of comparing computatlon tlmes and results associated

with the heuristic, an alternate fourth module was

constructed wlth all features of the heuristic dlsabled. The complete package, both with and without the heuristlc, was then applied to a scenario

typical of those for which the NASARC software Is

utilized.

A comparlson of results obtalned with and without the heurlstIc demonstrates that Improvement In

objective values is obtained at comparatively little computatlonal expense. An additional 25.43

CPU seconds on an Amdahl S860 Funning under the VM

operating system was required when the heuristic

was utilized. Thls tlme represents a somewhat conservative measure of the speed of the heurlstIc,

slnce both computational and noncomputational

(i.e., reporting) features associated wlth the heuristlc were disabled within the alternate module.

Resulting arrangements of arc segments within the

geostationary arc, and the objective values associated with each, are presented in TaD1e I.

Recalling that the objective is one of minimizlng an interference measure associated with

each arc segment, Table ] illustrates that objectives for segments 3, 4, 15, 16, 17, 23, and 24 are

Improved by application of the neuristic; objectives for segments 5, 6, 18, 19, 20, and 25 are

sllghtly worsened. However, the average _mprovement In objective value is 0.76, which more than

offsets the average degradation of 0.23. Examination of results obtained with the heuristic also

demonstrates that a degree of "levelllng" of objectlve values takes place. This is due to the fact

that the heurlstlc a11ows an interchange of two

schedule elemen_s_o proceed as long as the improvement gained In the obJectlve being examined offsets the possible degradation of any other single

objective value. Thls effect is desirable for this

application, in which scarce orbital arc resources

must be dlstrlbuted as equitably as possible.

6. CONCLUSIONS

An heuristic approach to solution of a class

of multiobJective n-job, l-machine schedullng problems has been presented. The scheduling problem is

formulated as a decision tree search problem, wlth

alternatlve schedules represented as alternative

orderings of jobs. A1ternatlve orderings are represented by nodes of a decision tree. Each node

Is reachable through feasible and efficient interchange of two schedule elements. The heurlstlc

approach to generation and utility assessment of

declslon tree nodes is two-stage. Stage I of the

heuristic ensures that only feasible and efficient

(Improved) nodes are generated. Stage II of the

heurlstlc ensures that only the most promising parent node of the current generation of nodes is

selected for application of Stage I in creatlon of

the next generation of nodes.

The heuristic has been implemented in a module

of the Numerical Arc Segmentation Algorlthm for a

Radio Conference (NASARC), a software package

developed for satellite systems planning purposes.

The problem formulation and heuristic have Important advantages In this appllcatlon. The problem

formulation allows substantlal simplification of

Interference relatlonships and solutlon approach.

The complexlty of calculatlng Interference relationshlps for a large number of satellite systems

Is avoided through the use of worst-case required

separatlons as an Interference measure In caiculatlng obJectlve function values. While this approach

Is certalnly not unlque to thls formulation (i.e.,

see [5]), It Is an Important feature. It Is expected that this feature of the problem formulation

may be applicable to a wide variety of scheduling

problems where minimization of job-to-job interference Is sought. The heurlstlc Is well suited to

thls type of problem because we seek improvement of

an Initial solution rather than absolute optimality.

The heurlstic allows a limlted degree of automated,
rule-baseddecislon-maklngappropriateto a multiobjectiveproblemvia Formulationof Improvement

measuresfor StageI andFormulationof preference

crlteria in StageII. Slncetheheuristictreats

theschedulingproblemasanorderingproblem,varlablesdescribingexactpositionsof eachschedule

elementneednot bedealt with, otherthanto the

extentneededIn makingminoradjustmentso accomplish aninterchange.Theheuristicalso tendsto

level objectiveFunctionvalues,whichis a desir- ablefeaturein caseswhereequitabletreatmentof

schedulelements(In termsof obJectlveFunction valueachieved)is a concern.Theheuristicprovidesaneasily implementedandefficient meansof

achlevingthe goalof anImprovedsolution,wlthout

dependence onsystem-resident optimlzatlonpackages.

ThisFeaturewasparticularly Importantfor NASARC,

whichwasInstalledona variety of computersystemsthroughouttheworldandwasrequiredto produceconsistentresults overall systemsonwhich

it wasimplemented.It Is expectedthat these

advantageswouldapplyIn thesolutionof scheduling problemsfor a varlety of otherapplications.

REFERENCES

Ill H. Emmons, "One-Machlne Sequencing to MInimlze Certain Functions of Job Tardiness,"

Oper. Res., vol. 17, no. 4, pp. 701-715,

July-Aug. 1969.

[2] J. Erschler, G. Fontan, C. Merce, and

F. Roubellat, "A New Dominance Concept in

Scheduling n Jobs on a Sln_le Machine wlth

Times and Due Dates," Oper. Res.,

vol 31, no. l, pp. I14-127, Jan.-Feb. 1983.

[3] S.C. Graves, "A Revlew of Production Scheduling," Oper. Res., vol. 29, no. 4, pp. 646-675,

July-Aug. 1981.

[4] J.P. Ignlzlo, "A Generallzed Goal Pro_rammlng

_roach to the Minimal Interference, Multicriteria Nxl Schedullng Problem," IEEE Trans.,

vol. 16, no. 4, pp. 316-322, Dec. 1984.

[5] E.L. Lawler, "Sequencing Jobs to Minlmlze

Total WeightedCompletlon Time Subject to

Precedence Constralnts," in Annals of

Discrete Mathematics 2. New York: NorthHolland Publisnlng Co., 1978, pp. 75-90.

[6] B. Ma]aKootl, "Theorles and an Exact Interactlve Palred-Comparison Approach for Discrete

Multiple-Criteria Problems," IEEE Trans. on

Syst. Man Cybernetics, vol. 19, no. 2,

pp. 365-378, Mar.-Apr. 1989.

[7] K.A. PaSch, "Heuristics for Job Shod Scheduling" Ph.D. Thesis, Massachusetts Inst. of

Technology, 198B.

[8] 3. Picard and M. Queyranne, "The TimeDependent TraveIInq Salesman Problem and Its

Application to the Tardlness Problem in OneMachine Scheduling," Oper. Res., vol. 26,

no. I, pp. 86-110, 3an.-Feb. 1978.

[9] S. Reiter and G. Sherman, "Discrete OptlmlzIng," SIAM J., vol. 13, no. 3, pp. 864-889,

Sept. 1965.

[I0] C.H. Reilly, "A Satelllte System Synthesis

Model for Orbltal Arc Allotment Optimlzation", IEEE Trans. Commun., vol. 36, no. 7,

pp. 845-849, July 1988.

[Ill L. Schrage and K.R. Baker, "Dynamic Programming Solution of Sequenclng Problems with

Precedence Constralnts," Oper. Res., vol. 26,

no. 3, pp. 444-449, May-June, 1978.

[12] W.A. Whyte, A.O. Heyward, D.S. Ponchak,

R.L. Spence, and J E. Zuzek, "Numerical Arc

Segmentatlon Algorithm for a Radlo/Conference

- NASARC (Version 2.0) Technical Manual "

[13]

NASA TM-IOOI60, 1987.

W.A. Whyte, A.O. Heyward, D.S. Ponchak,

R.L. Spence, and i.E. Zuzek, "Numerical Arc

Segmentatlon Algorithm for a Radio Conference

- NASARC (Verslon 2.0) User's Manual," NASA

TM-lOOl61, 1987.
TABLE 1

Arc Segment Arrangements

Segment

Index

Heuristic Heuristic Change in

Not Utilized Utilized Objective

Segment Objective

Location Value

(Longitude)

1 -168.00 -164.00 1.05

2 -119.00 -115.00 i.ii

3 -115.00 -iii.00 2.35

4 -III.00 -107.00 2.26

5 -107.00 -102.00 1.83

6 -102.00 -96.00 1.47

7 -96.00 -92.00 1.69

8 -88.00 -83.00 1.69

9 -78.00 -74.00 2.03

I0 -74.00 -70.00 2.30

ii -70.00 -66.00 1.74

12 -66.00 -62.00 0.98

13 -62.00 -59.00 0.19

14 -58.00 -55.00 0.22

15 -50.00 -44.00 2.10

16 -44.00 -41.00 3.18

17 -41.00 -35.00 2.10

18 -35.00 -29.00 1.64

19 -29.00 -25.00 1.40

20 -25.00 -16.00 1.20

21 -16.00 -9.00 1.18

22 -9.00 0.00 1.58

23 0.00 3.00 2.92

24 3.00 8.00 2.95

25 8.00 15.00 1.93

26 15.00 19.00 1.46

27 19.00 26.00 1.33

28 26.00 30.00 1.67

29 30.00 35,00 1.90

30 35.00 42.00 1.90

31 42.00 46.00 1.75

32 46.00 54.00 1.86

33 54.00 57.00 2.46

34 60.00 65.00 2.71

35 65.00 71.00 2.10

36 71.00 79.00 1.52

37 80.00 86,00 1.25

38 86.00 95,00 1.49

39 95.00 98.00 2.95

40 98.00 102.00 3.60

41 106.00 112.00 1.74

42 112.00 115.00 0.30

43 115.00 119.00 1.27

44 120.00 125.00 3.01

45 125.00 129.00 3.47

46 129.00 138.00 2.57

47 138.00 141.00 2.03

48 151.00 158.00 1.99

49 158.00 164.00 2.02

Segment segment Objective

Index Location Value

(Longitude)

1 -168.00

2 -119.00

3 -115.00

5 -IIi.00

4 -106.00

6 -102.00

7 -96.00

8 -88.00

9 -78.00

I0 -74.00

Ii -70.00

12 -66.00

13 -62.00

14 -58.00

15 -50.00

17 -44.00

18 -40.00

16 -37.00

19 -31.00

20 -25.00

21 -16.00

22 -9.00

23 0.00

25 3.00

24 10.00

26 15.00

27 19.00

28 26.00

29 30.00

30 35.00

31 42.00

32 46.00

33 54.00

34 60.00

35 65.00

36 71.00

37 80.00

38 86.00

39 95.00

40 98.00

41 106.00

42 112.00

43 115.00

44 120.00

45 125.00

46 129.00

47 138.00

48 151.00

49 158.00

-164

-115

-iii

-106

-102

-96

-92

-83

-74

-70

-66

-62

-59

-55

-44

-40

-37

-31

-25

-16

00

00

00

00

00

00

00

00

00

00

00

00

00

00

00

00

00

00

00

00

-9 00

0 00

3 00

I0 00

15 00

19 00

26 00

30 O0

35 O0

42 O0

46 O0

54 00

57 00

65 00

71.00

79.00

86.00

95.00

98.00

102.00

112.00

115.00

119.00

125.00

129.00

138.00

141.00

158.00

164.00

1.05

I.ii

2.19

2.11

1.92

1.56

1.69

1.69

2.03

2.30

1.74

0.98

0.19

0.22

0.76

1.34

1.94

1.96

1.48

1.29

1.18

1.58

2.44

2.47

1.94

1.46

1.33

1.67

1.90

1.90

1.75

1.86

2.46

2.71

2.10

1.52

1.25

1.49

2.95

3.60

1.74

0.30

1.27

3.01

3.47

2.57

2.03

1.99

2.02

-0.16

0.28

-0.34

0.09

-1.34

-0.76

0.30

-1.22

0.08

0.09

-0.48

0.54

-i.01
Initial Ordering: 1, 2, 3

3'1'2 _ O_ / 1'2'3 J

J,2

2,3,1 Q 3,1,2

)

) _) 1,U2,_ '3'1

(starred nodes indicate first occurrence of one of 3! possible ordedngs)

FIGURE 1, - DECIS[ONTREE REPRESENTINGALL POSSIBLESEOUENCESOF THREEJOBS.

Condition 1II-7

I I

T1 i _____ T2i I

_,7.__-___/._/_ T

Tlj I I 2j

I r r 1

I 1 2 I

max(T ,T )__--___ min(T ,T )

ti lj I_ t 2i 2j

I I

I I

t _ t I

li I 2i i

I t _t

I lj I 2j

___///////_"_"1 max(t ,t )

/

2i 2j

I I

I I

rain ( tli. tlj)

FIGURE 2, - FEASIBILITYCONDITIONSFOR ALLOWABLE [NTERCHANGEOF JOBSWITHIN SCHEDULE.
Joblndex

Sequence lndex

Objective Values

Prior to Interchange

i-1 i i+1 j-1 j j+l

E ,w I E +w I E +w 1 IE +w I_ +w I E +w I

[ H,i H,i-2l i,1+1 i,H I i+1.i+2I+1,i I j-1.j p1,j-2 j j+l j. j-1I j+l,j+2 j+l,j I

Job lndex

Sequence lndex

Objective Values

After Interchange

i-1 j i+1 j-1 i j+l

FIGURE 3. - OBJECTIVE VALUES AFFECTED BY INTERCHANGE OF JOBS WITHIN SCHEDULE.

i-1 r=-

_7/'////_1 I

1

I

L

1i+1 j-1

L_V///////_///////////////////M I

b,,

i

j+l

t _./i//,//////_

I

J i+1 _ __,,. j-I i j+l

I l___J____ II.....__L_____/"J_.,/M

FIGURE q. - INTERCHANGE OF SCHEDULE ELEMENTS ACCOMPANIED BY LATERAL SHAFT OF ADJACENT ELEMENTS.

I0
NationalAeronautics and

SpaceAdrninislration

1. Report No.

NASA TM- 102367

4. Title and Subtitle

Application of a Hybrid Generation/Utility Assessment Heuristic

to a Class of Scheduling Problems

7. Author(s)

Ann O. Heyward

9. Performing Organization Name and Address

National Aeronautics and Space Administration

Lewis Research Center

Cleveland, Ohio 44135-3191

12. Sponsoring Agency Name and Address

National Aeronautics and Space Administration

Washington, D.C. 20546-0001

3. Recipient's Catalog No.

5. Report Date

September 1989

Report Documentation Page

2. Government Accession No.

6. Performing Organization Code

8. Performing Organization Report No.

E-5086

10. Work Unit No.

643-10-01

11. Contract or Grant No.

13. TyPe of Report and Period Covered

Technical Memorandum

14. Sponsoring Agency Code

15. Supplementary Notes

Prepared for the International Conference on Systems, Man, and Cybernetics, sponsored by the Institute of

Electrical and Electronics Engineers, Cambridge, Massachusetts, November i4-17, 1989

16. Abstract

A two-stage heuristic solution approach for a class of multiobjective, n-job, 1-machine scheduling problems is

described. Minimization of "job-to-job" interference for n jobs is sought. The first stage generates alternative

schedule sequences by interchanging pairs of schedule elements. The set of alternative sequences can represent

nodes of a decision tree; each node is reached via decision to interchange job elements. The second stage selects

the parent node for the next generation of alternative sequences through automated paired comparison of objective

performance for all current nodes. An application of the heuristic to communications satellite systems planning is

presented.

17. Key Words (Suggested by Author(s))

Scheduling

Heuristic

Multiple objectives

18. Distribution Statement

Unclassified- Unlimited

Subject Category 66

19. Security Classif. (of this report) 20. Security Classif. (of this page) 21. No of pages

Unclassified Unclassified 12

NASAFORM162SOCT86 *For sale by the National Technical Information Service, Springfield, Virginia 22161

22. Price*

A03