The Optimal Algorithm of a Two-Stage Flow Shop Problem with Infinite Number of Jobs


Article Preview

In this paper, a two-machine two-stage flow shop with identical jobs is considered. Each of identical jobs 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. The problem is to determine the assignment of the flexible tasks to the machines for each job, with the objective of maximizing the throughput rate. This model is applied to the graphic programs processing which comprises data processing and graphics processing. We consider three cases regarding the capacity of the buffer between the machines with infinite number of jobs. We present optimal algorithm for each variant of the problem.



Edited by:

Di Zheng, Yiqiang Wang, Yi-Min Deng, Aibing Yu and Weihua Li




Q. Wei and Y. Wu, "The Optimal Algorithm of a Two-Stage Flow Shop Problem with Infinite Number of Jobs", Applied Mechanics and Materials, Vols. 101-102, pp. 290-293, 2012

Online since:

September 2011





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

[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] S.M. Johnson: Naval Research Logistics Quarterly, Vol. 1(1954), pp.61-68.

[5] Y. Crama and H. Gultekin: Journal of scheduling, Vol. 13(2009), pp.227-243.