How to program a schedule...

Question

Hello! I have to build a program that schedules based on certain rules. I'm not sure how to explain it, so let me give you an example..

You have Five People A,B,C,D,E. And you Have another set of people S1 S2 S3 S4 S5 S6 S7.

If A B C D and E are available every hour from 9 to 5, and S1 S2 S3 S4 S5 S6 and S7 have a list of 3 people they want to see from {A,B,C,D,E}

That's my problem and I'm not sure where to begin...

Thanks for your help!

Answer 1

Here's one approach:

Start with S1, assign him the three people he wants at 9am, then go to S2 and try to schedule his meeting at 9am. Continue until you have a conflict, then move that meeting to 10am. Return to 9am for the next one. If there is a conflict at 10 also, move to 11, etc.

Once the program tries to schedule a meeting after hours, you'll know you've hit a case where all the meetings aren't possible in a single day.

Answer 2

There's quite a bit to be said about scheduling algorithms, so for your own sake you might want to crack open your text (or at least do some wiki-research) and get a feel for the most common techniques.

Personally, I'd start by considering the functions you need to have available to create this schedule.

For example, you need a a function along the lines of def testAppointment(meetingSubject, meetingTime): that tests whether or not a given appointment is valid.

You might also want a function def listAvailableTimes(meetingSubject)): that returns a list of every time that a particular meeting subject has available.

Do you see where I'm going with this? Build up the functions that give you the information needed to solve the problem, then go about your "main loop," so to speak.

Answer 3

Here's some python code that will do the trick. You will want to update VISITOR_PEOPLE. And if some people get to schedule before others, you'll need to reorder VISITOR_IDS.

Edit: I added some more code to account for the fact that people can't be in a different place at the same time. You might want to make that more efficient (i.e. don't try to schedule a time that will not work). I'll let you figure that out though ;)

import sys

HOURS = ['9:00AM', '10:00AM', '11:00AM', '12:00PM', '1:00PM', '2:00PM', '3:00PM', '4:00PM']
PEOPLE_IDS = ['A', 'B', 'C', 'D', 'E']
VISITOR_IDS = ['S1', 'S2', 'S3', 'S4', 'S5', 'S6', 'S7']
VISITOR_PEOPLE = {'S1': ['A', 'B', 'C'], 
                  'S2': ['A', 'D', 'E'], 
                  'S3': ['B', 'E', 'D'], 
                  'S4': ['D', 'E', 'A'], 
                  'S5': ['C', 'D', 'E'], 
                  'S6': ['A', 'D', 'C'], 
                  'S7': ['B', 'C', 'D']
                  }

def main():
    people = {}
    for id in PEOPLE_IDS:
        people[id] = Person(id)
    visitors = {}
    for id in VISITOR_IDS:
        visitors[id] = Visitor(id, VISITOR_PEOPLE[id], people)
    for v in visitors.values():
        v.printSchedule()

class Person:
    def __init__(self, id):
        self.id = id
        self.schedule = [False]*8  # False = free, True = busy
    def scheduleTime(self):
        # schedules next available hour and returns that hour
        for i in range(len(self.schedule)):
            if not self.schedule[i]:
                self.schedule[i] = True
                return HOURS[i]
        return 'unavailable'
    def unscheduleTime(self, index):
        self.schedule[index] = False

class Visitor:
    def __init__(self, id, people_requests, people):
        self.id = id
        self.schedule = {} # {person_id: hour}
        for p in people_requests:
            bad_times = set()  # times that Visitor is busy
            time = people[p].scheduleTime()
            while time in self.schedule.values():  # keep scheduling a time until you get one that works for both the Visitor and Person
                bad_times.add(time)
                time = people[p].scheduleTime()
            self.schedule[p] = time
            for t in bad_times:  # unschedule bad_times from Person
                people[p].unscheduleTime(HOURS.index(t))
    def printSchedule(self):
        print 'Schedule for %s [Person (time)]:' % self.id
        for p,t in self.schedule.items():
            print '    %s (%s)' % (p,t)

if __name__ == '__main__':
    sys.exit(main())