otero1991's blog

Greedy problem??
By otero1991, 12 years ago, In English

I have spent some days thinking this problem but I couldn't found the solution!! I think it's greedy!! The problem is: There are some tasks of four different types: AB,BA,A and B. This tasks must be solved using two machines MA and MB. Tasks of type A must be solved on machine MA and tasks of type B must be solved on machine MB. Tasks of type AB, have two parts, part A must be solved on machine MA and part B must be solved in machine MB, but part B can't start until the part A is completed, and similar with tasks of type BA. Each task has its processing time in each machine, and each machine can run at most one task at the same time. Compute the minimal time to finish all the tasks

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please give a link to the problem.

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it +7 Vote: I do not like it

This problem belongs to class of scheduling problems and has name J2|n <  = 2|Cmax in Graham's notation.

It is solved by reducing this problem to F2||Cmax problem, which is pretty famous, and can be solved in time. See Peter Brucker's "Scheduling algorithms" book for further clarification.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What do you mean with "J2|n <  = 2|Cmax in Graham's notation"

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      I already found what you said, thank you very much!!!, it's a very good book

      → Reply