2
$\begingroup$

I am implementing a Branch-and-Bound algorithm to find the optimal solution for the Flowshop Scheduling Problem, but I am stuck on the optimization phase, here is a rundown of the problem and what I go so far.

(I am sorry for my English, not a native speaker...)

The Problem

There are n tasks that must be run through two different machines, $m_1$ and $m_2$, where each tasks has different durations in each machine, minimize the sum of the finishing time of each task on $m_2$.

$\min c^* = \sum_{i=0}^{n} f_{2i}$

Where

$f_{ij}$ = the finishing time of task j on machine i

$d_{ij}$ = the duration of task j on machine i

With the constraint that each task can only be run in $m_2$ after it's done running on $m_1$.

What I have so far

I nailed down the basics of BnB, I can compute a dual bound for any node (a value that is no greater than the optimal solution from that node onwards). Then for each node, I generate all of it's children by appending one of the tasks that are not yet scheduled to the end of the task list, for each child I compute the dual bound and each one of them that has a dual bound greater than the greatest up to now its put on a priority queue. This solves the problem, every time I find a node with a dual bound that's better than the one I have, I am zeroing in the optimal solution, and each node that produces a dual bound that doesn't add any information for me is not explored (ie, bounds that are lower than the current optimal, since it doesn't help to narrow the possible value for the real optimal)

What I need

Now I need to add pruning by using the primal bound, in this case the primal bound for a node is any viable solution that's a child of that node, this yields a value that's certainly greater than or equal to the optimal, the reasoning here is: if I pick a feasible solution that's not the optimal, then by definition, its cost must be greater than the optimal, otherwise I picked the optimal solution, but it's value is, by definition, no less than the optimal

This is where I need help, is this the correct way to bound the optimal value? I only expand nodes in which the dual bound (an estimative of the lowest value I can achieve from that node) are between the best dual and primal bound so far in the tree? Can I ignore any nodes where the dual bound is outside this range? I can't seem to get my code right, but that's because I am unsure whats the correct line of thought here.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.