6

I am working on a problem similar to the assembly line scheduling by dynamic programming.The issue is that unlike the classic problem where we have predefined stations now I only have information which task should run before which other(could be more than one) tasks.

I have to find out which tasks to put on which line to minimize the total time taken by the production.So obviously if the tasks are on a single line then they are executing in serial fashion and hence are slower.

So I have following issues

  1. How do I create time based levels/lines as I don't have a sequence of all tasks? I only know which task comes before which(one or many) tasks. Time based levels are necessary as I have to minimize the time (which would happen when the tasks are executed in parallel).
  2. How do I determine the optimal order of tasks to minimize time? As several tasks would be waiting for a single task, I have to minimize this time as well.
  3. Like the original problem, communication between different lines would also have a cost. I have to determine whether this communication cost is worth moving the task to a separate line(from its communicating task)

tl;dr: A parallel version of the assembly line scheduling (Dynamic programming) where all lines could be busy at the same time and I don't have any station numbering/ordering. I just know which tasks should be executed before which.

I have to decide which tasks to put on the same line and which tasks to put on the different lines (given the communication time when tasks are on different lines) to minimize the production time.

gnat
  • 21,442
  • 29
  • 112
  • 288
  • What is the relation between the time and communication costs? Is 10 time and 5 communication better or worse than 5 time and 10 communication - and why? And how many lines do you have at most? Without the communication, you could use as many lines in parallel as you have leaf nodes in your task dependency tree otherwise. – Frank Nov 28 '13 at 13:00
  • The communication cost would be added to the execution time.The communication cost would only be used if the communicating functions are on separate lines.The communication times and execution times would be added to the total process time.Currently I am considering two lines but in the future it should be expandable to any number of lines.The issue is I have to take care of dependencies.e.g.Fitting a tire in a car cant be done before creating a tire.The communication time would be added to the execution time just like in the classic version(replacing line change time with communication time) –  Nov 28 '13 at 13:14
  • 1
    Is that like what you are looking for (exchange line switch cost with comm. cost)? http://www.geeksforgeeks.org/dynamic-programming-set-34-assembly-line-scheduling/ – Frank Nov 28 '13 at 13:44
  • This is the classic assembly line scheduling problem.I am looking to make a parallel implementation.See my question for details. –  Nov 28 '13 at 13:52

1 Answers1

1

If you are willing to accept a good-enough answer, you could treat it as a combinatorial optimization problem. Create in memory, a tree of possible solutions. The first branches in the tree is the assignment of the next task or tasks to available assembly lines. Based on a chain of dependencies established as tasks enter the system, you always know the "next" task or tasks. If the "next" task is one of several, you might want to make the larger task the priority.

The nodes at the next depth of the tree consist of the possibilities for the assignment of the next task (which line it is assigned to).

Since this leads to a explosion of possibilities, with the tree quickly growing large, you need to periodically prune the tree. If there are any assignments which would never make sense, you should not add those assignments to the tree.

When the tree becomes too large, in terms of memory usage, or at some arbitrary depth, prune the tree to a single leaf: compute the cost (efficiency) of each leaf, take the best one, and throw away all the others. Starting from that leaf, compute a new set of branches, and so on.

Frank Hileman
  • 3,922
  • 16
  • 18