# how to tackle this combinatorial algorithm problem

Filed under:
|
##### algorithm-design

I have `N` people who must each take `T` exams. Each exam takes "some" time, e.g. 30 min (no such thing as finishing early). Exams must be performed in front of an examiner.

I need to schedule each person to take each exam in front of an examiner within an overall time period, using the minimum number of examiners for the minimum amount of time (i.e. no examiners idle)

There are the following restrictions:

• No person can be in 2 places at once
• each person must take each exam once
• noone should be examined by the same examiner twice

I realise that an optimal solution is probably NP-Complete, and that I'm probably best off using a genetic algorithm to obtain a best estimate (similar to this? http://stackoverflow.com/questions/184195/seating-plan-software-recommendations-does-such-a-beast-even-exist).

I'm comfortable with how genetic algorithms work, what i'm struggling with is how to model the problem programatically such that i CAN manipulate the parameters genetically..

If each exam took the same amount of time, then i'd divide the time period up into these lengths, and simply create a matrix of time slots vs examiners and drop the candidates in. However because the times of each test are not necessarily the same, i'm a bit lost on how to approach this.

currently im doing this:

• make a list of all "tests" which need to take place, between every candidate and exam
• repeatedly loop over all examiners, for each one: find an unscheduled test which is eligible for the examiner (based on the restrictions)
• continue until all tests that can be scheduled, are
• if there are any unscheduled tests, increment the number of examiners and start again.

i'm looking for better suggestions on how to approach this, as it feels rather crude currently.

© Stack Overflow or respective owner

• #### Need help with fixing Genetic Algorithm that's not evolving correctly

as seen on Stack Overflow - Search for 'Stack Overflow'
I am working on a maze solving application that uses a Genetic Algorithm to evolve a set of genes (within Individuals) to evolve a Population of Individuals that power an Agent through a maze. The majority of the code used appears to be working fine but when the code runs it's not selecting the best… >>> More

• #### How should I Test a Genetic Algorithm

as seen on Stack Overflow - Search for 'Stack Overflow'
I have made a quite few genetic algorithms; they work (they find a reasonable solution quickly). But I have now discovered TDD. Is there a way to write a genetic algorithm (which relies heavily on random numbers) in a TDD way? To pose the question more generally, How do you test a non-deterministic… >>> More

• #### A detail question when applying genetic algorithm to traveling salesman

as seen on Stack Overflow - Search for 'Stack Overflow'
I read various stuff on this and understand the principle and concepts involved, however, none of paper mentions the details of how to calculate the fitness of a chromosome (which represents a route) involving adjacent cities (in the chromosome) that are not directly connected by an edge (in the graph)… >>> More

• #### Do you have genetic algorithm in production?

as seen on Stack Overflow - Search for 'Stack Overflow'
Is it good idea to use genetic algorithm in production? If you are using it: In what case? What pros for selecting subj? Can you easily add changes to algorithm? >>> More

• #### Automatic test data generation using genetic algorithm in MATLAB

as seen on Stack Overflow - Search for 'Stack Overflow'
I am doing my project in software testing. Genetic algorithm is the technique I want to use to generate automatic test data\test cases in MATLAB. Please help me in doing my project successfully. >>> More

• #### Solutions for exercises in The Algorithm Design Manual

as seen on Stack Overflow - Search for 'Stack Overflow'
Does anybody know where to find solutions for the exercises in the book The Algorithm Design Manual? >>> More

• #### Algorithm design, "randomising" timetable schedule in Python although open to other languages.

as seen on Stack Overflow - Search for 'Stack Overflow'
Before I start I should add I am a musician and not a native programmer, this was undertook to make my life easier. Here is the situation, at work I'm given a new csv file each which contains a list of sound files, their length, and the minimum total amount of time they must be played. I create… >>> More

• #### Disk Search / Sort Algorithm

as seen on Stack Overflow - Search for 'Stack Overflow'
Given a Range of numbers say 1 to 10,000, Input is in random order. Constraint: At any point only 1000 numbers can be loaded to memory. Assumption: Assuming unique numbers. I propose the following efficient , "When-Required-sort Algorithm". We write the numbers into files which are designated… >>> More

• #### Algorithm for dynamic combinations

as seen on Stack Overflow - Search for 'Stack Overflow'
My code has a list called INPUTS, that contains a dynamic number of lists, let's call them A, B, C, .. N. These lists contain a dynamic number of Events I would like to call a function with each combination of Events. To illustrate with an example: INPUTS: A(0,1,2), B(0,1), C(0,1,2,3) I need to… >>> More

• #### Dynamic programming practice problems with solutions

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi, I have seen many questions on stackoverflow where dynamic programming technique can be used to make a exponential algorithm, a polynomial one. I have seen standard problems on dynamic programming. Is there a website or book that contains practice problems and solutions? Thanks Bala >>> More