Given the processing times for parts to be manufactured in different machines in a flow shop line, depending on the sequence in which the parts are manufactured, the makespan (i.e. the total time that elapses from the beginning to the end) can be reduced. The lower bound is the minimum value of the makespan.
I don't think that this is what you want. You may want to find a GOOD lower bound on the optimal value. This may be tricky, as the problem is NP-hard - see the article
Article A note on the complexity of flow-shop scheduling with deteri...
that I was involved in writing. Depending on how you formulate your problem - i.e., depending on the variable definition - you may reach a lower bound that is better than another, equivalent in the IP sense, formulation. The tighter you want it to be, the harder it may be to find it - that's what you need to pay for when working on NP-hard problems. :-)
The solution to NP-hard problems are usually difficult to determine using a local technique or straightforward reduction algorithm. Greedy assignment will not yield an optimal solution. Therefore, to determine the lower bound for makespan for scheduling a flow shop line, it is better to compare the solution strength of different creative algorithms/metaheuristic techniques.
Regards,
Modestus.
Dear Joao,
To get the lower bound (LB) you can take any approximation algorithm with a guaranteed accuracy (F^0-F*=F^0–D, i.e., LB=F^0–D. Similarly, if you take an approximation algorithm such that (F^0-F*)/F*=M/2. Calculate a_j=\SUM_{L=1}^m p_jL and b_j=\SUM_{L=m+1}^M p_jL. Consider the two-machine flow shop problem with the processing times of jobs equal to a_j and b_j for the first and for the second machine respectively. This problem is O(n log n) solvable (Johnson's algorithm). Let F^0 is the corresponding value of the minimum makespan. Then for the initial M-machine flow shop problem we have F*>=F^0/m, i.e., LB= F^0/m.
You are better off using discrete event simulation modelling. The free basic versions of most simulation software packages can do this. You can then use the results to generate whatever equations you need, that is if you still need them after getting a solution.
Dear Yakov M. Shafransky,
Thanks for your explanation. I have the following doubt, and I hope you can help me: consider a flow shop line with 4 machines. The times to manufacture 3 jobs in the 4 machines are the following:
J1 = {5; 8; 2; 7}
J2 = {4; 5; 7; 2}
J3 = {6; 4; 9; 8}
The minimum makespan (which is the lower bound) is 36, and it can be obtained with Johnson's algorithm (sequence J1 -> J3 -> J2). It is not clear how your proposed procedure can be used to determine the value of 36 for this problem.
Dear Joao,
You are right, 36 is a lower bound. More than that, it seems, it is an optimal value (that is also a LB, of cause). If you use the algorithm that I mentioned, you will obtain the sequence (J2, J3, J1) with the makespan value 40. Respectively, LB=20. It is also a lower bound (not so good as 36, but it is a LB).
The mentioned algorithm is one of the simplest. If you take an approximate algorithm with a better quality, you will have a better LB.
P.S. You can also use some well-known LB: LB=max{max{\SUM_{j=1}^n p_{jL}: L=1,...,M}; max{\SUM_{L=1}^M p_{jL}: j=1,...,n}}. For your instance, e.g., LB=27.
To obtain a better LB, you can find some different LBs and choose the LB with the maximum value.
Dear Yakov M. Shafransky,
Thanks for your reply. Actually, I am really interested in an algorithm to determine the minimum makespan (which in this case is equal to 36). Your proposed algorithm does not lead to the result I want. I would be grateful if you can inform me an algorithm to determine the minimum makespan.
Dear Joao,
So, the correct formulation of your question is finding an algorithm that solves the problem to the optimum (or calculates the minimum value of the makespan, not just a LB).
As it was mentioned in some earlier answers to your question, the problem is NP-hard (even in the strong sense) if M>2. It means that there cannot exist a fast (polynomial) exact algorithm (unless P = NP). To find an optimal solution (optimal value), different branch-and-bound algorithms or dynamic programming approach and their modifications are used. Also, metaheuristics are popular but they do not guarantee obtaining an optimal solution.
Thanks again. I believe Johnson's algorithm will be Ok for what I need.
Johnson's algorithm is Ok if M=2, otherwise, I do not know, what you have in mind.
- Badges
- Science topic
- Similar topics
- Econ
- Manufacturing