首頁‎ > ‎電子期刊‎ > ‎2005 年 第 12 期‎ > ‎

多角調課演算法初探(七)


摘要

  • 文章編號:20050904
  • 投稿日期:2005/08/25
  • 作者:董世尊、廖韋傑、陳冠廷、陳雅鳳
  • 備註:


壹、前言

在上一期期刊中,提到Sunset的排課系統的調課部份主要的表單及模組的相關運作,而本期要介紹的是排課系統中,無論是調課、代課、自動排課…等都需要運作到的主要類別核心—scheduler模組中的調課部份,以及整個排課系統的大致架構。


貳、排課系統架構

排課的系統中,主要的重點作業就是排程的問題,排程是在某一個時間點上,發生某一件事情,這件事情會有參與的人、發生的地點、發生的事情、誰在接受 此件事。應用在排課上就會由教師、班級、科目、場地來組成並將一個事件(包括:教師、班級、場地、科目)的限制條件全都排入到分課表裡,最後才將時間排入 分課表。


Sunset系統裡的物件類別模組中有許多的類別,這些類別包括:Appointment、Appointments、CEvent、CEvents、 Distance、Distances、Location、Locations、Period、Periods、Scheduler、 TimeTable、TimeTables、Variable、Variables、What、Whas、Where、Wheres、Who、Whos、 Whom、Whoms。


在Sunset系統裡最主要的核心是在Scheduler的部分, Scheduler一開始會將所有要排的課 (CEvent)、所有的教師(Whos)、所有的教室(Wheres)、所有的班級(Whoms)載入。載入後可以選擇一些事件來自動排課後,可測試某 一個事件排在星期幾的第幾節是否可行;可以鎖定事件、事件屬性變更、新增事件、取得教師某一段的空閒時間、檢查事件是否可調換並取得解決方案。使用者通常 都是透過表單來呼叫Sceduler運行整個系統。


在類別中的CEvent主要事在取得分課表裡的東西,包含分課編號、教師編號、場地編號、科目編號、班級編號、星期、節次、節數、優先權、星期條件、節次條件、是否跨中午、科目是否可重複、單雙週;系統會將所有事件的這些東西儲存至 CEevents。


Appointment是一個記錄時間的資料物件,在記錄排課資源(Who、What、Where、Whom…等)的開始時間、持續時間、星期幾、單雙 週、科目、是否鎖定…等。TimeTable是由很多的Periods來組成。一個Periods由許多的Period組成。Who( What、Where、Whom…)類別是一個集合物件,可用來儲存很多的教師(科目、教室、班級),系統再將所有教師集合到Whos( Whats、Wheres、Whoms…)類別裡。利用這樣的邏輯、分工作業方式組成排課系統,這就是排課系統的整個大致架構。

參、Scheduler模組解析-調課部份

Scheduler模組中的TestScheduler中,主要是當兩節課在比對之時,就會傳值進入此Function做條件判斷的檢查,來找到可調換或不可調換的符合結果。(圖一)

Private Function TestSchedule(ByVal NewEvent As CEvent, ByVal WeekDay As Integer, ByVal PeriodNo As Integer) As Integer

    Dim intTempVal As Integer

    Dim bPass As Boolean

    Dim prdBreak As Period

    Dim prdTest As Period

    Dim prdsTest As Periods

Set evtTested = Nothing

   

    With NewEvent

    Set whrTest = IIf(IsNullValue(.WhereID), Nothing, mWheres(CStr(.WhereID)))

    Set whmTest = IIf(IsNullValue(.WhomID), Nothing, mWhoms(CStr(.WhomID)))

    Set whoTest = IIf(IsNullValue(.WhoID), Nothing, mWhos(CStr(.WhoID)))

à判斷場地、班級、教師是否有值

    Set prdsTest = mTimeTables(CStr(.TimeTableID)).Periods

                                                   à取得時間表的值

    Set prdBreak = prdsTest.GetBreakPeriod(WeekDay) à取得某星期午休時段

    Set prdTest = prdsTest.GetPeriod(WeekDay, PeriodNo)

    If prdTest Is Nothing Then

        TestSchedule = tsCannotFità傳入參數=8,在其他模組需要時傳入其值並顯示「太胖了,塞不下」字樣

        Exit Function

    End If

   

    Set prdsUse = New Periods

    prdsUse.Add prdTest

    bPass = ((Not (prdBreak Is Nothing)) And (Not .AllowLongBreak)) And (.Length > 1)

    If bPass Then bPass = ((prdTest.BeginTime - prdBreak.BeginTime) < 0)

                                      à利用bPass的判斷,來檢查是否有跨中午的情況

   

For intTempVal = PeriodNo + 1 To PeriodNo + .Length - 1

        Set prdTest = prdsTest.GetPeriod(WeekDay, intTempVal)

        If prdTest Is Nothing Then

            TestSchedule = tsCannotFit

            Exit Function

        End If

        If Not whrTest Is Nothing Then

            If Not (IsNullValue(prdTest.LocID) Or IsNullValue(whrTest.LocID)) Then

                If prdTest.LocID <> whrTest.LocID Then

                    TestSchedule = tsLocConflict

                    Exit Function

                End If

            End If

        End If

        prdsUse.Add prdTest

    Next intTempVal à檢查場地與節次之間的有效性,並讓三節連續課程,一節一節的陸續加入做檢查。

   

   If bPass Then

        If (prdTest.BeginTime - prdBreak.BeginTime) > 0 Then

            TestSchedule = tsLongBreak

            Exit Function

        End If

    End Ifà檢查跨中午條件

   

        If .WeekDayOp > 0 Then

        If IsNumeric(.WeekDayVar) Then

            Select Case .WeekDayOp

                Case opEqual

                    bPass = (WeekDay = CInt(.WeekDayVar))

                Case opGreater

                    bPass = (WeekDay > CInt(.WeekDayVar))

                Case opGreaterOrEqual

                    bPass = (WeekDay >= CInt(.WeekDayVar))

                Case opLess

                    bPass = (WeekDay < CInt(.WeekDayVar))

                Case opLessOrEqual

                    bPass = (WeekDay <= CInt(.WeekDayVar))

                Case opNotEqual

                    bPass = (WeekDay <> CInt(.WeekDayVar))

                Case Else

                    bPass = True

            End Select

            If Not bPass Then

                TestSchedule = tsWeekDayConflictà傳入參數1,星期條件不符。

                Exit Function

            End If

        ElseIf .WeekDayOp = opEqual Then

            If mWVar.Exists(.WeekDayVar) Then

                If Not mWVar(.WeekDayVar).Fit(WeekDay) Then

                    TestSchedule = tsWeekDayConflictà傳入參數1,星期條件不符。

                    Exit Function

                End If

            End If

        End If

    End Ifà判斷是否有星期條件

………

……

………

    If Not whmTest Is Nothing Then

        If .AllowDuplicate Then

    intTempVal=whmTest.Appointments.CheckWhom(prdsUse, NullValue, .WeekFlag)

        Else

            intTempVal=whmTest.Appointments.CheckWhom(prdsUse, .WhatID, .WeekFlag)

        End If

        If intTempVal <> 0 Then

            Select Case intTempVal

                Case 1

                TestSchedule = tsWhomConflictà傳入參數5,已排其他科目,請勿插隊。

                Case 3

                    TestSchedule = tsDupWhatà傳入參數6,科目重覆。

                Case Else

                TestSchedule = tsWhomConflictà傳入參數5,已排其他科目,請勿插隊。

            End Select

            Exit Function

        End If

    End Ifà檢查班級及科目是否允許重覆排課之情況發生。

   

    If Not whrTest Is Nothing Then

        If Not whrTest.LocOnly Then

            If whrTest.Capacity > 1 Then à whrTest.Capacity是指此場地的容納量。

                intTempVal = 1

                bPass = False

                Do Until intTempVal > whrTest.Capacity

                    whrTest.UseAppointments intTempVal

                    If whrTest.Appointments.IsFreePeriods(prdsUse, .WeekFlag) Then

                        nWhereAvailable = intTempVal

                        bPass = True

                        Exit Do

                    End If

                    intTempVal = intTempVal + 1

                Loop

                If Not bPass Then

                TestSchedule = tsWhereConflictà傳入參數7;場地已滿。

                    Exit Function

                End If

            ElseIf Not whrTest.Appointments.IsFreePeriods(prdsUse, .WeekFlag) Then

                TestSchedule = tsWhereConflictà傳入參數7;場地已滿。

                Exit Function

            End If

        End If

    End If

   

    If Not whoTest Is Nothing Then

        If  whoTest.Capacity > 1 ThenàwhoTest.Capacity是指某位老師所教的班級數量

            intTempVal = 1

            bPass = False

            Do Until intTempVal > whoTest.Capacity

                whoTest.UseAppointments intTempVal

         If whoTest.Appointments.CheckWho(prdsUse, mDistances, .WeekFlag) = 0 Then

                    nWhoAvailable = intTempVal

                    bPass = True

                    Exit Do

                End If

                intTempVal = intTempVal + 1

            Loop

            If Not bPass Then

                TestSchedule = tsWhoConflictà傳入參數3;本尊太忙,分身乏術。

                Exit Function

            End If

        Else

………

……

………

End Function

 

  • 圖一、TestScheduler

肆、結論

在上述的TestScheduler在調課中扮演著重要的角色,而其模組的其他Function也在整個排課系統中運作著許多主要功能,包括資料的 載入,自動排課的相關要素條件判斷…等,所以Scheduler算是在整個系統中為核心部份,因此我們也將套用之前所預設好的演算法架構進行修改,嚐試使 多角調課作業得以順利進行。

Comments