많은 변수로 시간 설정 문제 해결하기

Question

변수 클래스 (~ 100), 객실 (20), 용어 (8) 및 평일 (5)으로 구성된 고전적인 시간 지정 문제가 있습니다.

문제를 단순화하기 위해 다음과 같이 제한 사항을 줄입니다.

하루는 9 시간입니다.

일부 수업은 학생에게 필수이며, 1,3,5,7 (및 2,4,6,8)의 필수 수업은 서로 겹치지 않아야합니다.

클래스 일부는 3

어떤 클래스가 특정 객실에 있어야하며, 일부 2 시간이며, 시간의 측면에서 서로 다른 가중치를 가지고있다.

동일한 강의 시간에 2 강의를 진행할 수 없습니다.

저는 logilabs python constraint 모듈을 사용할 것입니다. 그리고 나는 변수와 영역을 현명하게 chosing하는 것이 문제를 해결할 시간이 적다는 것을 알고 있습니다. 문제는 전에 제약 프로그래밍을 한 적이 없으며 어디서 무엇을 시작해야 하는지를 알아 내기 위해 문제를 구축하는 데 어려움을 겪고 있습니다. 예를 들면 다음과 같습니다.

"같은 방의 같은 클래스가 아니며 같은 날이 서로의 시간대에 겹칠 수 있습니다"와 같은 제약 조건을 설정할 수 있습니다. 아니면 "방이 같은 날에 예약 된 시간이 9 시간을 초과 할 수 없습니다"라는 메시지로 시작한 다음 축소 된 솔루션 도메인을 계속 사용하십시오. 나는 첫 번째 제약 조건이 다른 제약 조건보다 해결하는데 더 오래 걸릴 것이라고 추정한다 (시도하지 않았다). 하지만 변수와 솔루션 영역을 변경하거나 작은 문제를 재구성해야합니다. 난 이미있어 변수, 도메인, 간격, 구현 등 손실 약간

길고도 짧은 이야기, 난 등 현명 변수를 chosing,

감사 문제, 솔루션 도메인을 구축하기위한 몇 가지 포인터를 필요

UPDATE

t 한 번 봐 내가 기본 응용 프로그램을 만들어 github

Answer 1

에 업로드 한 logilab - 제약 패키지를 사용하여 그는 curriculum course example code의 Drools Planner입니다. 기본적으로는 똑같지 만 용어는 약간 다릅니다. 각 코스 (= 클래스)는 강의실 (= 방)과 기간 (= 각 요일의 각 학기는 기간)으로 예약해야하는 강의가 많이 있습니다.

트릭은 도메인 모델을 깨끗하게 유지하고 제약 조건 규칙과 별도로 유지하는 것입니다. 수업은 시간적으로 다른 가중치를 사용하기 때문에 Lecture에만 startingPeriod이 할당되어 강의를 다른 기간으로 이동하는 코드는 많지 않습니다 (처음 기간 만 재 할당).

Answer 2

"변수를 현명하게 선택"및 "선택 영역을 줄이는"번들로 끝났습니다.

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 년,이 과정은 월요일 또는 화요일에있을 수 있습니다 등 "으로, 클래스에 기본 제약을 내장했습니다 아래는 장고 기반 timetabling 응용 프로그램에서 미리보기 내가 뭘입니다 2 또는 3 방 1 또는 2 또는 3 또는 4 또는 5 "에서 데이터베이스에서 코스를 선택할 때 처음에이 기본 제약 조건을 직접 적용 할 수 있습니다.

"같은 날에 같은 방에 같은 방에 두 개의 코스가있을 수 없음"과 같은 일반 제약 조건이 데이터베이스에서 수행 된 선택에서 오는 축소 된 가변 도메인에 적용됩니다.

현재 작동 중입니다.