×

zbMATH — the first resource for mathematics

Flexible flow shop with dedicated buffers. (English) Zbl 1412.90051
Summary: A two-stage flexible flow shop is considered, where first- and second-stage machines form disjoint pairs, each with a buffer. The buffer capacity varies from pair to pair, and the buffer requirement varies from job to job. Each job is to be assigned to a pair of machines for processing and uses the required amount of buffer from the start till the end of its processing. Operations have equal duration. It is shown that, unless \(\mathrm{P} = \mathrm{NP}\), no polynomial-time algorithm guarantees a makespan less than \(4 / 3\) of the optimal. The paper presents two integer linear programs, compared by means of computational experiments. Both approaches utilise as a subroutine the developed polynomial-time algorithm for the case of equal buffers.
MSC:
90B35 Deterministic scheduling theory in operations research
68Q25 Analysis of algorithms and problem complexity
90C10 Integer programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Blazewicz, J.; Ecker, K. H.; Pesch, E.; Schmidt, G.; Weglarz, J., Handbook on Scheduling: From Theory to Applications, (2007), Springer-Verlag Berlin Heidelberg
[2] Blazewicz, J.; Kubiak, W.; Szwarcfiter, J., Scheduling unit-time tasks on flow-shops under resource constraints, Ann. Oper. Res., 16, 1, 255-266, (1988) · Zbl 0694.90065
[3] Blazewicz, J.; Lenstra, J. K.; Kan, A. R., Scheduling subject to resource constraints: classification and complexity, Discrete Appl. Math., 5, 1, 11-24, (1983) · Zbl 0516.68037
[4] Fung, J.; Singh, G.; Zinder, Y., Capacity planning in supply chains of mineral resources, Inform. Sci., 316, 397-418, (2015)
[5] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness, (1979), W. H. Freeman · Zbl 0411.68039
[6] Hall, P., On representatives of subsets, J. Lond. Math. Soc., 10, 1, 26-30, (1935) · JFM 61.0067.01
[7] Kononov, A.; Hong, J. S.; Kononova, P.; Lin, F. C., Quantity-based buffer-constrained two-machine flowshop problem: active and passive prefetch models for multimedia applications, J. Sched., 15, 4, 487-497, (2012) · Zbl 1280.90056
[8] Kononova, P. A.; Kochetov, Y. A., The variable neighborhood search for the two machine flow shop problem with a passive prefetch, J. Appl. Ind. Math., 7, 1, 54-67, (2013)
[9] Korte, B.; Vygen, J., Combinatorial Optimization, (2012), Springer · Zbl 1237.90001
[10] Lin, F. C.; Hong, J. S.; Lin, B. M.T., A two-machine flowshop problem with processing time-dependent buffer constraints - An application in multimedia presentations, Comput. Oper. Res., 36, 4, 1158-1175, (2009) · Zbl 1162.90460
[11] Lin, F. C.; Hong, J. S.; Lin, B. M.T., Sequence optimization for media objects with due date constraints in multimedia presentations from digital libraries, Inf. Syst., 38, 1, 82-96, (2013)
[12] Pinedo, M., Scheduling Theory, Algorithms, and Systems, (2012), Springer: Springer New York · Zbl 1239.90002
[13] Röck, H., Some new results in flow shop scheduling, Z. Oper. Res., 28, 1, 1-16, (1984) · Zbl 0529.90059
[14] S. Sevastyanov, B.M.T. Lin, F.J. Hwang, Makespan minimization in parallel flow shops, in: The 9th Workshop on Models and Algorithms for Planning and Scheduling Problems, 2009, pp. 244-246.
[15] Süral, H.; Kondakci, S.; Erkip, N., Scheduling unit-time tasks in renewable resource constrained flowshops, Z. Oper. Res., 36, 6, 497-516, (1992) · Zbl 0794.90026
[16] Szwarcfiter, J. L., Job shop scheduling with unit time operations under resource constraints and release dates, Discrete Appl. Math., 18, 2, 227-233, (1987) · Zbl 0636.90046
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.