Published on

26-Jun-2016View

216Download

4

Transcript

Discrete Opti

s a

igu

nce an

ity, 4

003;line 2

ods of time and S(s = 1, 2, . . . ,S) venues, whereN = T = 2S, N/2 competitions are played ineach period and each competition takes place at a

eserved.

* Corresponding author. Fax: +65 68220777.E-mail address: br@smu.edu.sg (B. Rodrigues).

European Journal of Operational Rese0377-2217/$ - see front matter 2005 Elsevier B.V. All rights r1. Introduction

Sports competition scheduling has attractedmuch interest among researchers. In a number ofstudies, including Ball and Webster [3], De Werra,Jacot-Descombes and Masson [17], Russell andLeung [15], Nemhauser and Trick [12] and Henz[6], each team to be scheduled is assumed to have

its own competition venue. Recently, motivatedby the request from a head coach of a major col-lege football team to have teams participate at ven-ues twice and compete against each other at leastonce, where any two teams should not competetwice at the same venue and where all teams com-pete at all times, Urban and Russell [16] proposeda multi-venue problem where venue comes intoplay as part of the scheduling process.

In Urban and Russells model, given N (i =1, 2, . . . ,N,N is even) teams, T(t = 1, 2, . . . ,T) peri-Abstract

In this work, we study scheduling sports competitions at multiple venues, a problem recently introduced by Urbanand Russell [T.L. Urban, R.A. Russell, Scheduling sports competitions on multiple venues, European Journal of Oper-ational Research 148 (2003) 302311]. The distinguishing feature of the problem is that venues come into play whenscheduling. We develop beam search and simulated annealing approaches to the problem and its extension. Computa-tional experiments were conducted and algorithms compared and analyzed. We found that the simulated annealingalgorithm with specialized neighborhood moves achieved superior solutions in signicantly shorter times than themethod of Urban and Russell. 2005 Elsevier B.V. All rights reserved.

Keywords: Scheduling; Sports management; Beam search; Meta-heuristicScheduling sports competition

A. Lim a, B. Rodra Department of IEEM, Hong Kong University of Scieb School of Business, Singapore Management Univers

Received 11 September 2Available ondoi:10.1016/j.ejor.2005.03.029mization

t multiple venuesRevisited

es b,*, X. Zhang a

d Technology, Clearwater Bay, Kowloon, Hong Kong

69 Bukit Timah Road, Singapore 259756, Singapore

accepted 16 March 20053 June 2005

arch 175 (2006) 171186

www.elsevier.com/locate/ejor

to handle the extended problem which takes into

these techniques.

Lemma 1. In any optimal solution, no constraint in

(5) and (6) is violated for N 6 20, given k1 = 1,k2 = 10 and k3 = 100.

This follows from the fact that if any constraintin (5) and (6) is violated, the solution will cost atleast 10 but from the experimental results in Sec-tion 4 and Appendix A we know that solutionsfor N 6 20, are less than 10. We note that evenwith other settings of k1, k2 and k3 Lemma 1 holdsas long as k2 P 2k1 and k P 2k1. Lemma 1 can beapplied to more general cases where constraints orobjectives are ranked in a hierarchy, and the objec-tive is to satisfy as many high-priority constraints

peraparticular venue. The objective is to nd a feasibleschedule that satises all the constraints, or to min-imize a penalty when constraints are violated. Tak-ing p to represent a match between a pair of teams,e.g., p = (i, j) is a match between teams i and j, andPi to represent the set of competitions in which teami participates, we can formulate the problem as

minimize Z X

i

Xs

k1d1is Xp

k2d2p

Xp

Xs

k3d3ps 1

s:t:Xp

xpst 1 for all s; t 2XpP i

Xs

xpst 1 for all i; t 3Xp2P i

Xt

xpst d1is P 2 for all i; s

4Xs

Xt

xpst d2p P 1 for all p 5X

t

xpst d3ps 6 1 for all p; s 6

xpst f0; 1g for all p; s; t 7

where xpst = 1 if competition p is held at venue sand in time period t, and 0 otherwise. In the for-mulation above, constraint set (2) ensures that ateach venue during each time period, there is ex-actly one competition. Constraint set (3) speciesthat each team can only compete once during eachtime period and (4) requires that each team playsat least twice at each venue, where otherwise a pen-alty (k1d1is) will be added to the cost function.Constraint set (5) requires that each team playsevery other team at least once, where otherwise apenalty (k2d2p) is incurred and (6) requires that amatch should not occur at the same venue morethan once, where otherwise a penalty (k3d3ps) is in-curred. In the above model, d1, d2 and d3 are setsof deviation variables used to measure the corre-sponding constraint violations [16]. In the prob-lem, these variables were set to reect thepriorities established by the decision maker where

172 A. Lim et al. / European Journal of Ok1 = 1, k2 = 10 and k3 = 100. As an example, theaccount practical aspects from a variety of situa-tions. In Section 4, computational results are com-pared and analyzed. A short conclusion in given inSection 5.

2. Solution approaches

Beam Search (BS) and Simulated Annealing(SA) are applied to the multi-venue problem wherethe following are used to facilitate implementingschedule given in Table 1 is an optimal solutionwith Z = 0 for N = 10, S = 5 and T = 10.

In this work, we apply a construction heuristicand a meta-heuristic method to the problem inSection 2. In Section 3, the methods are modied

Table 1An optional schedule for N = 10, S = 5 and T = 10

Period Venue

1 2 3 4 5

1 (8, 9) (1, 2) (3, 6) (4, 5) (7, 10)2 (4, 9) (5, 6) (7, 8) (2, 10) (1, 3)3 (3, 10) (1, 8) (2, 7) (5, 9) (4, 6)4 (5, 6) (3, 8) (4, 10) (1, 7) (2, 9)5 (4, 7) (6, 10) (3, 9) (1, 2) (5, 8)6 (1, 10) (3, 4) (2, 5) (6, 9) (7, 8)7 (1, 5) (9, 10) (4, 8) (3, 7) (2, 6)8 (2, 8) (5, 7) (1, 6) (3, 4) (9, 10)9 (2, 3) (7, 9) (5, 10) (6, 8) (1, 4)10 (6, 7) (2, 4) (1, 9) (8, 10) (3, 5)

tional Research 175 (2006) 171186as possible or to minimize (or equivalently, maxi-

peramize) high-priority objectives rst. Thus, Lemma 1can be used if the primary objective is to minimizethe number of violated constraints in set (6), whilethe secondary objective is to minimize the numberof violated constraints in set (5), and lastly to min-imize those violated in set (4). This is the underlin-ing reason why penalty coecients were set to bek1 = 1, k2 = 10 and k3 = 100.

From Lemma 1, it is easy to derive the follow-ing lemmas:

Lemma 2. In any optimal solution, all competitions

(i, j) with i < j occur once in the solution, and theremaining N/2 competitions are in {(i, i + 1)ji is odd,1 6 i 6 N}.

Lemma 3. There exists an optimal solution such

that the competition played at Venue 1 in Period 1is p = (1, 2) where competitions played at Venues 1

to S in Period 1 can be sorted in lexicographic order.

Lemma 4. There exists an optimal solution with the

following property: competitions in the first period

are generated from one of 2S2 sequences byexchanging 2x with 2x + l(2 6 x 6 S 1) fromthe original sequence (1, 2, 3, 4, 5, . . . ,N 2, N 1, N).

Lemma 3 is derived by swapping competitionsbetween two periods or two venues. Lemma 4 re-sults from Lemma 3 and renumbering takingadvantage of symmetries between teams. WithLemma 4, the possible choices of competitionsfor Period 1 are reduced from N!/2S to 2S2. Forthe case N = 6, the reduction is from 90 = 720/8to 2 = 232. The two sequences are (1, 2, 3, 4, 5, 6)and (1, 2, 3, 5, 4, 6), which correspond to the twoschedules {(1, 2), (3, 4), (5, 6)} and {(1, 2), (3, 5),(4, 6)}, respectively.

2.1. Using beam search

BS [11,14] expands only the p most promisingnodes at each depth level of Breadth First Search(BFS) and thus avoids the combinatorial explosionproblem of BFS. For the multi-venue problem,each of the T S games Gt,s ordered by the periodnumber t and, in case of ties, the venue number s,

A. Lim et al. / European Journal of Ocorresponds to a depth level of BS. Initially, thebeam search procedure assigns (1, 2) to the rstgame G1,1, i.e. the competition at Venue 1 duringPeriod 1, and thus generates the initial parent.For every subsequent step, the procedure expandsat most b children from each parent of the previ-ous step. At this time, the b children are simplythose matches with the smallest local evaluationcost, L = hv, f, sdi, in the lexicographic order.

In the denition of L, m is the objective value ofthe partial schedule, i.e. the penalties specied bythe problem denition. However, with only thevalue of m the algorithm is unable to distinguishmore promising child nodes, especially in earlystages of the BS procedure when most nodes havea m value of 0. Hence, f and sd are used to furtherdierentiate nodes. For each venue s, fs is the dier-ence between the number of competitions that maytake place at s in future time periods and the num-ber of required competitions at s. For example, ifcompetitions {(1, 3), (2, 4), (3, 4)} are allowed totake place at Venue 1 and one more competitionis required at Venue 1, f1 is thus 2 (i.e. 3 1).The overall f of the partial schedule is then takento be the smallest fs for all s (1 6 s 6 S). Next, letvisiti,s denote the number of times team i has playedat venue s, and let remaini,s = max(2 visiti,s, 0).For each venue s, sds is the standard deviation ofremaini,s for all i (1 6 i 6 N). The overall standarddeviation, sd, of the partial schedule is then denedas sum of sds for all s.

The rationale behind using f in L is to maxi-mize possible choices of future competitions ateach venue, and thus to increase the chance ofnding better complete schedules. Meanwhile,the aim in using sd is to distribute teams moreevenly among venues so that nal schedules aremore balanced. In addition, the L of a child nodecan be eciently computed from its parent nodewith a time complexity of O(N).

The at most p b children of the current step, de-noted as the cth step, are then sorted according totheir overall evaluation cost, O, and only the best pare retained which, in turn, serve as parent nodesin the (c + 1)th step. In view of the tight constraintsof themulti-venue problem, a look-ahead procedureis necessary both to ensure the feasibility of resultingsolutions and to improve their quality. More pre-

tional Research 175 (2006) 171186 173cisely, when calculating the overall evaluation cost

of an expanded child, the procedure greedily con-structs at most d more games forward from the cthstep. The overall evaluation cost O is a function ofLs at the cth and (c + d)th-depth levels, denotedLc and Lc+d, respectively. A simple way to calculateO is by the formula O = w1 Lc + w2 Lc+dwhere w1 + w2 = 1. The underlining rationale is totake into account estimated future costs of currentchoices, instead of depending entirely on the Lc atthe current depth. In our experiments, the para-meters p, b, d, w1 and w2 were set as 2000, 10, 5, 0.5and 0.5, respectively.

Take the instance N = 8 as an example and letp = b = d = 2. In Fig. 1, for the 6th step, two chil-dren nodes are generated from each parent nodeinherited from the 5th step. The look-ahead proce-dure is then applied to all four children and com-putes their overall evaluation costs. With the

cepted with probability P expcostS0costS=T expD=T , where cost(S) denotes the cost of the cur-rent solution S, cost(S 0) denotes the cost of thenext solution S 0, D is the dierence of these costs

,6) (7,8)

,6) (7,8),4)

,6) (7,8),4) (5,6)

(1,2)

.00>

(1,2) (3,4) (5,6) (7,8)(6,8)

(1,2) (3,4) (5,6) (7,8)(6,8) (1,2)

(1,2) (3,4) (5,6) (7,8)(6,8) (1,5)

(1,2) (3,4) (5,6) (7,8)(6,8) (1,2) (3,4)

(1,2) (3,4) (5,6) (7,8)(6,8) (1,5) (2,3)

(1,2) (3,4) (5,6) (7,8)(6,8) (1,2) (3,4) (5,7)

(1,2) (3,4) (5,6) (7,8)(6,8) (1,5) (2,3) (4,7)

.87>

Step 5 (1,2) (3,4) (5,6) (7,8)(7,8)

(1,2) (3,4) (5,6) (7,8)(7,8) (5,6)

(1,2) (3,4) (5,6) (7,8)(7,8) (1,2)

Step 1 (1,2)

(1,2) (3,4) (5,6) (7,8)(6,8)

Step 6

Fig. 2. The beam search tree.

174 A. Lim et al. / European Journal of Operational Research 175 (2006) 171186overall evaluation cost array [h0,18.5, 1.94i, h0,18, 1.94i, h0,15, 2.04i, h0,15, 2.04i], the algo-rithm selects the 1st and 2nd child for the 6th step,which results in the beam search tree as illustratedin Fig. 2. The same process is repeated for theremaining steps until it reaches complete schedules.

2.2. Using simulated annealing

In implementing SA [8], moves that lead to asolution worse than the current solution are ac-

Children

Step 5

Lc+d

Look-Ahead

(1,2) (3,4) (5,6) (7,8)(7,8)

(1,2) (3,4) (5,6) (7,8)(7,8) (5,6)

(1,2) (3,4) (5(7,8) (1,2)

(1,2) (3,4) (5,6) (7,8)(7,8) (5,6) (1,2)

(1,2) (3,4) (5(7,8) (1,2) (3

(1,2) (3,4) (5,6) (7,8)(7,8) (5,6) (1,2) (3,4)

(1,2) (3,4) (5(7,8) (1,2) (3

Step 1

in [18,2,10]. This move randomly selects two peri-ods, and then exchanges some competitions duringthe rst period with the same number of matchesin the second period, while ensuring that eachteam can only compete once during each time per-iod. In Fig. 5, two matches are exchanged betweenPeriod 2 and Period 3, i.e., matches (5, 8) and (1, 4)are moved to Period 3, while matches (1, 5) and(4, 8) are moved to Period 2. The new venues ofthe exchanged matches are sequentially assignedaccording to their original orders. As in the givenexample, the venue number of match (5, 8) is al-ways smaller than that of (1, 4) before and afterthe Partial Period Exchange operation. The cost

Fig. 3. Simulated annealing scheme.

A. Lim et al. / European Journal of Operational Research 175 (2006) 171186 175at the end of Step 2a is unchanged for a speciednumber of consecutive temperatures. The numberis 200 for the algorithm. The inner loop criterionexecutes the loop a constant (Loop) number oftimes with the value Loop at about 300 and thenew temperature in Step 2b is calculated byT 0 = rT, where r is 0.999.

The remaining component for the SA algorithmis the neighborhood structure used where threeneighborhood moves are employed. The rst localmove is a Venue Exchange move which randomlyselects a period and then exchanges the venues oftwo matches in the selected period. In Fig. 4, twomatches which take place at Venue 2 and 3 inthe same period are exchanged. The cost dier-ence, D, resulting from a Venue Exchange movecan be computed with time complexity of O(l).

The second local move is a Partial Period Ex-change move, which is similar to moves describedVenuePeriod1 2 3 4

1 (5,8) (1,4) (2,6) (3,7)

Fig. 4. Venue e

VenuePeriod1 2 3 4

2 (5,8) (1,4) (2,6) (3,7)3 (1,5) (3,7) (4,8) (2,6)

Fig. 5. Partial peridierence, d, resulting from a Partial Period Ex-change move can be computed with time complex-ity of O(N).

The last local move is an Opponent Exchangemove which randomly selects a period and then ex-changes the opponents of two matches in the se-lected period. In Fig. 6, the two matches (1, 4)and (2, 6) which take place in the same periodarc changed to (1, 2) and (4, 6). Dierent fromVenue Exchange and Partial Period Exchange,Opponent Exchange enables the algorithm tointroduce new matches and to remove old ones.The cost dierence, d, resulting from an OpponentExchange move can be computed with time com-plexity of O(1).

Moreove...