Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Now there are n independent projects, each project is composed by several steps, each step is labeled, there are k workers are going to work on these projects. Assume that each person can do only one step, and each step can only be done by a specific worker(it will be declared in input file). Each project has a order for its steps, for example, workers can operate the second step only if the first step has been done. when one person finished one step, then he can be assigned to another step immediately.

Task:Input the number of projects, and the number of steps of each project, and the worker corresponds to each step, and how much time it will take to finish the step. Try to find an algorithm to calculate the optimized time to finish all projects. Example inputs:

2 3(2 projects, 3 workers)

3 1 2 2 3 3 5(for project 1, there are 3 steps, the first will be done by worker 1 takes 2 hours, the second will be done by worker 2 by 3 hours, the third will be done by worker 3 by 5 hours)

2 2 3 3 2(for project 2, there are 2 steps, the first will be done by worker 2 by 3 hours, the second will be done by worker 3 by 2 hours)

Output 11 ( the minimized hours to finish the whole project)

share|improve this question

closed as off-topic by Ricardo Andrade, Andrey Rekalo, Olivier Benoist, Stefan Kohl, Willie Wong Nov 28 '13 at 12:47

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question does not appear to be about research level mathematics within the scope defined in the help center." – Ricardo Andrade, Andrey Rekalo, Olivier Benoist, Stefan Kohl, Willie Wong
If this question can be reworded to fit the rules in the help center, please edit the question.

1  
It would really help if you could tell me why you need to solve this. Is this a problem in a programming class? (If so, please give a link to the class webpage.) Are there any helpful constraints (eg do the workers always follow each other in numbered order (as in your example))? Is this a special case of a more general problem you are thinking about? –  Sam Nead Nov 26 '09 at 16:33
1  
This question is being flagged as off-topic or potentially homework. I'm not going to use moderator powers to close, however, at least for now. You may get better answers, and fewer downvotes, by asking the question more clearly (and perhaps in better english!). –  Scott Morrison Nov 29 '09 at 6:02
    
suggest migrate to Computer Science –  vzn Feb 14 at 0:15

1 Answer 1

up vote 2 down vote accepted

I think this is a member of a class of problems called scheduling problems. In particular I think it is the job shop scheduling problem. There are machines instead of people but the basic structure is the same. If I am right about this the prospects of a solution of this type of problem is bleak as problems with three machines have been proven to be strongly NP-hard. I have found a reference for this _Handbook of scheduling: algorithms, models, and performance analysis_By Joseph Y-T. Leung I was able to look at parts of it on google books.

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.