構建帶有大量變量的時間表問題

我有一個由變量類（〜100），房間（20），項（8）和工作日（5）組成的經典時間表問題。構建帶有大量變量的時間表問題

爲了簡化問題，以下是約束條件的減少。

一天是9個小時。

有些課程對學生來說是強制性的，而1,3,5,7（和2,4,6,8）的強制課程不能相互重疊。

類有不同的權重以小時計，有的2個小時，有些是3

一些類應該是在特定的房間。

同一時間同一班不能有兩場講座。

我正在用logilabs python約束模塊。我知道明智地選擇變量和領域將導致解決問題的時間更少。問題是我之前從來沒有做過約束編程，並且很難建立問題以找出開始的地點和內容。例如：

我可以設置一個約束條件，如「沒有兩個班級，同一個房間，同一天可以重疊彼此的時間段」。或者從「沒有房間可以在同一天預留超過9小時」開始，然後繼續使用縮小的解決方案域。我估計（沒有嘗試）第一個約束比另一個約束需要更長的時間來解決。但它也需要（我猜）改變變量和解決方案域或重建一個較小的問題。我已經是位變量，域，間隔，實現等失去

長話短說，我需要建立的問題，解決方案領域，艇員選拔變量明智地等

由於一些指針

UPDATE

使用logilab約束包我做了一個基本的應用程序並將其上傳到github

來源

2011-05-07 hinoglu

看看在t他的Drools Planner。它基本上是一樣的，但術語稍有不同：每門課程（=課程）都有一些需要安排到房間（=房間）和期間（=每個工作日的每學期是一段時間）的講座。

訣竅是保持一個乾淨的領域模型，並保持與約束規則分開。由於您的課程在小時數方面有不同的權重，因此我建議Lecture僅分配startingPeriod，因此將演講稿移至另一組期間（僅重新分配第一期）並不是很多代碼。

來源

2011-05-08 13:46:47

謝謝。實施永遠是我更好的起點:) – hinoglu 2011-05-09 10:46:11

我已經結束了一個解決方案，它捆綁了「明智地選擇變量」和「減少選擇域」。以下是基於Django的時間表應用我做的片段：

class Course(models.Model): 
    name = models.CharField(max_length=255, null=False, blank=False) 
    duration = models.PositiveSmallIntegerField(blank=False) 
    type = models.ForeignKey(CourseType, blank=False, null=False) 
    mandatory = models.BooleanField(default=False) 
    ''' 
     following are the basic constraints 
    ''' 
    days = models.ManyToManyField(Day, blank=True, null=True) 
    terms = models.ManyToManyField(Term) 
    rooms = models.ManyToManyField('ClassRoom', blank=True, null=True) 


    def __unicode__(self): 
     return u'%s' % self.name

我已經嵌入了基本約束到類，如「這當然可能是在週一或週二，在條款1或2或3 在房間1或2或3或4或5「，這使我可以直接應用這些基本約束，從數據庫選擇課程的開始。

一般的約束條件，比如「在同一天的同一小時之間沒有兩個課程可以在同一個房間內」，這些約束被應用於來自數據庫中所做選擇的減少的可變域。

似乎現在工作。

來源

2011-05-11 11:37:48 hinoglu

構建帶有大量變量的時間表問題

回答

相關問題