An Optimal Algorithm for a Special Flow Shop Problem with Infinite Buffer Capacity

Abstract:

In this paper, a two-machine flow shop problem with infinite buffer capacity is considered. Each of jobs is identical and has two tasks. The first task can be processed on either machine, called flexible task, while the second task must be processed on the second machine and can't be processed unless the first task has been processed. There is infinite buffer capacity between two machines. The problem is to determine the assignment of the flexible tasks to the machines for each job, with the objective of maximizing the makespan. We present an optimal algorithm for this problem.

• Periodical: Applied Mechanics and Materials (Volumes 101-102)
• Pages: 379-382
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.101-102.379
• Online since: September 2011
• Authors: Qi Wei
• Keywords: Hybrid Flow Shop, NP-Hard, Optimal Algorithm, Scheduling

References

[1] Q. Wei and Y. He: Applied Mathematics A Journal of Chinese Universities, Vol. 20(2005), pp.393-400.

[2] K. Panagiotis and V. George: IIE Transactions, Vol. 30(1998), pp.735-746.

[3] G. Vairaktarakis and C. Y. Lee: Naval Research Logistics, Vol. 51(2004), pp.44-59.

[4] J. Ostolaza, J.O. McClain and J. Thomas: Journal of Manufacturing and Operations Management, Vol. 3(1990), pp.105-133.

[5] S.M. Johnson: Naval Research Logistics Quarterly, Vol. 1(1954), pp.61-68.