Home
Search
 
What's New
Index
Books
Links
Q & A
Newsletter
Banners
 
Feedback
Tip Jar
 
C# Helper...
 
XML RSS Feed
Follow VBHelper on Twitter
 
 
 
MSDN Visual Basic Community
 
 
 
 
 
TitleGenerate a schedule for pool play on a single court with fairly distributed rests
DescriptionThis example shows how to generate a schedule for pool play on a single court with fairly distributed rests in Visual Basic 6.
Keywordspool, schedule
CategoriesAlgorithms, Miscellany
 
Suppose you have a 6 team pool on a single court and each team should play every other team. There are 6 * 5 / 2 = 15 matches. Each team plays 5 games so each team will rest for 10 games. The goal is to find a schedule that evenly distributes the rest periods so no team plays too many games in a row. This program finds an optimal solution by examining every possible schedule and pickinbg the one that is best.

When you click the Go button, the program performs some setup work and then calls subroutine GenerateSolution.

Subroutine GenerateSolution checks to see whether the complete schedule is assigned and, if it is, calls subroutine CheckSchedule to examine the schedule. If the current schedule is not complete, then GenerateSolution picks two teams to play in the current round and then calls itself recursively to fill in later rounds. The code performs some basic checks to ensure that it doesn't pick two teams that have already played each other.

 
' Teams m_CurrentSchedule(r, 1) and
' m_CurrentSchedule(r, 2) play in round r.
Private m_CurrentSchedule() As Integer

Private m_BestScheduleValue As Double
Private m_BestSchedule() As Integer

Private m_ScheduleNum As Long
Private m_NumSchedules As Long
Private m_ScheduleMod As Long

Private Sub cmdGo_Click()
Const INFINITY As Double = 1E+300
Dim num_teams As Integer
Dim num_rounds As Integer
Dim txt As String
Dim r As Integer

    txtResults.Text = ""
    Screen.MousePointer = vbHourglass
    DoEvents

    ' Make room for the schedules.
    num_teams = CInt(txtNumTeams.Text)
    num_rounds = (num_teams * (num_teams - 1)) \ 2
    ReDim m_CurrentSchedule(1 To num_rounds, 1 To 2)
    ReDim m_BestSchedule(1 To num_rounds, 1 To 2)
    m_BestScheduleValue = -INFINITY

    ' Examine schedules.
    m_ScheduleNum = 0
    m_NumSchedules = Factorial(num_rounds)
    m_ScheduleMod = 10 ^ Int(Log(m_NumSchedules) / Log(10) _
        - 2)
    GenerateSchedule 1, num_teams, num_rounds

    ' Display the best schedule.
    txt = "Best Schedule (value " & m_BestScheduleValue & _
        ")" & vbCrLf
    For r = 1 To num_rounds
        txt = txt & "    " & m_BestSchedule(r, 1) & " v " & _
            m_BestSchedule(r, 2)
    Next r

    txtResults.Text = txt
    Screen.MousePointer = vbDefault
End Sub

' Pick teams for this round and examine the resulting
' schedule.
Private Sub GenerateSchedule(ByVal round As Integer, ByVal _
    num_teams As Integer, ByVal num_rounds As Integer)
Dim team1 As Integer
Dim team2 As Integer
Dim ok_match As Boolean
Dim r As Integer

    ' See if we have a full schedule.
    If round > num_rounds Then
        CheckSchedule num_teams, num_rounds
        Exit Sub
    End If

    For team1 = 1 To num_teams - 1
        For team2 = team1 + 1 To num_teams
            ' See if we can match team1 and team2.
            ok_match = True
            For r = 1 To round - 1
                ' Make sure this match hasn't already been
                ' played.
                If m_CurrentSchedule(r, 1) = team1 And _
                   m_CurrentSchedule(r, 2) = team2 _
                Then
                    ok_match = False
                    Exit For
                End If
            Next r

            ' Try matching team1 and team2.
            If ok_match Then
                m_CurrentSchedule(round, 1) = team1
                m_CurrentSchedule(round, 2) = team2

                GenerateSchedule round + 1, num_teams, _
                    num_rounds
            End If
        Next team2
    Next team1
End Sub
 
Subroutine CheckSchedule calls function CurrentScheduleValue to get the current schedule's value. If the value is greater than the previous schedule's value, it saves the new schedule.
 
' See if the current solution is better than the best so
' far.
Private Sub CheckSchedule(ByVal num_teams As Integer, ByVal _
    num_rounds As Integer)
Dim current_value As Double
Dim r As Integer

    m_ScheduleNum = m_ScheduleNum + 1
    If m_ScheduleNum Mod m_ScheduleMod = 0 Then
        Me.Caption = m_ScheduleNum & "/" & m_NumSchedules
        Me.Refresh
    End If

    ' Get the current schedule's value.
    current_value = CurrentScheduleValue(num_teams, _
        num_rounds)

    ' See if this is an improvement.
    If m_BestScheduleValue < current_value Then
        m_BestScheduleValue = current_value
        For r = 1 To num_rounds
            m_BestSchedule(r, 1) = m_CurrentSchedule(r, 1)
            m_BestSchedule(r, 2) = m_CurrentSchedule(r, 2)
        Next r
    End If
End Sub
 
Function CurrentScheduleValue determines the value of the current schedule. It uses function TeamValue to see how much each team values the current schedule. It then adds up the sum of the squares of their values and the average value. The idea is that in a fair schedule each team's value should be close to the same.
 
' Return the value of the current solution.
' The value is the sum of the squares of the differences
' between the team's
' values and their average. For example, if a team's value
' is 6 and the average
' is 4, the total value increases by (6-4)^2 = 2^2 = 4.
' Here low values are good because it means each team has
' about the same value.
Private Function CurrentScheduleValue(ByVal num_teams As _
    Integer, ByVal num_rounds As Integer) As Double
Dim team As Integer
Dim team_value() As Double
Dim total_value As Double
Dim ave_value As Double

    ' Make room for each team's value.
    ReDim team_value(1 To num_teams)

    ' Evaluate each team's value.
    total_value = 0
    For team = 1 To num_teams
        team_value(team) = TeamValue(team, num_teams, _
            num_rounds)
        total_value = total_value + team_value(team)
    Next team

    ' Combine the teams' values.
    ave_value = total_value / num_teams
    total_value = 0
    For team = 1 To num_teams
        total_value = total_value + (ave_value - _
            team_value(team)) ^ 2
    Next team

    ' Return a negative value so bigger values are better.
    CurrentScheduleValue = -total_value
End Function
Private Function Factorial(ByVal n As Integer) As Long
Dim result As Long
Dim i As Integer

    result = 1
    For i = 2 To n
        result = result * i
    Next i

    Factorial = result
End Function
 
Function TeamValue calculates the value of the current schedule for a particular team. Ideally the team plays only 1 game in a row with rests between and then length of each rest period in games is the same. The function calculates the sum of the differences squared between the scheduled play and rest periods and their ideal lengths.

This routine is the most confusing and the most important. It determines what the program think is important for picking a good schedule.

 
' Return the schedule's value to this team.
' The value is the sum of the squares of the differences
' between the team's
' lengths of rest and play runs and the ideal values. For
' example, if the
' ideal rest length is 2 games and the team has a rest of 4
' games, the
' value is (4-2)^2 = 2^2 = 4. Here low values are good.
Private Function TeamValue(ByVal team As Integer, ByVal _
    num_teams As Integer, ByVal num_rounds As Integer)
Dim num_played As Integer
Dim num_rested As Integer
Dim ideal_rest As Double
Dim ideal_play As Double
Dim cost_rest As Double
Dim cost_play As Double
Dim r As Integer
Dim was_playing As Boolean
Dim now_playing As Boolean
Dim current_run As Integer

    ' Every team plays (num_teams - 1) games.
    ' There are a total of num_rounds = (num_teams *
    ' (num_teams - 1))/2 games.
    ' Every team rests for num_rounds - num_played games.
    ' E.g. for 6 teams, every team plays 5 games, there are
    ' a total of 15 games, and each team rests for 10 games.
    ' The ideal rest schedule occurs when rests are spread
    ' equally between played games
    ' = num_rest_games / num_played
    num_played = num_teams - 1
    num_rested = num_rounds - num_played
    ideal_rest = num_rested / num_played

    ' Ideally we play 1 game in a row.
    ideal_play = 1

    ' Compare the team's play and rest streaks to the
    ' ideals.
    ' See if we rest or play in the first round.
    was_playing = _
        (m_CurrentSchedule(1, 1) = team) Or _
        (m_CurrentSchedule(1, 2) = team)

    ' Check other rounds.
    current_run = 1
    For r = 2 To num_rounds
        now_playing = _
            (m_CurrentSchedule(r, 1) = team) Or _
            (m_CurrentSchedule(r, 2) = team)

        ' See if we are starting or ending a rest.
        If now_playing = was_playing Then
            ' Continue the current streak.
            current_run = current_run + 1
        Else
            ' We are starting or ending a rest.
            If was_playing Then
                ' We were playing.
                cost_play = cost_play + (current_run - _
                    ideal_play) ^ 2
            Else
                ' We were resting.
                cost_rest = cost_rest + (current_run - _
                    ideal_rest) ^ 2
            End If

            current_run = 1
            was_playing = now_playing
        End If
    Next r

    ' Handle the final play or rest.
    If was_playing Then
        ' We were playing.
        cost_play = cost_play + Abs(current_run - _
            ideal_play) ^ 2
    Else
        ' We were resting.
        cost_rest = cost_rest + Abs(current_run - _
            ideal_rest) ^ 2
    End If

    ' Return the rest cost plus the play cost.
    TeamValue = cost_play + cost_rest
End Function
 
Unfortunately there are a lot of possible schedules to examine so this program only works for relatively small schedules. An algorithm more intelligent than just examining every possible schedule will be much faster.
 
 
Copyright © 1997-2010 Rocky Mountain Computer Consulting, Inc.   All rights reserved.
  Updated