-3
$\begingroup$

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)

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ 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? $\endgroup$
    – Sam Nead
    Commented Nov 26, 2009 at 16:33
  • 1
    $\begingroup$ 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!). $\endgroup$
    – Kim Morrison
    Commented Nov 29, 2009 at 6:02
  • $\begingroup$ suggest migrate to Computer Science $\endgroup$
    – vzn
    Commented Feb 14, 2014 at 0:15

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged .