×

Two-machine flowshop scheduling in a physical examination center. (English) Zbl 1416.90014

Summary: In this paper, we formulate two important operational processes of the physical examination center as a group scheduling problem in two-machine flowshop. The objective is to minimize the makespan. We first analyze the complexity of the problem with a fixed number of release dates and present a pseudo-polynomial-time algorithm. Then we provide an approximation algorithm and analyze its worst-case error bounds for the problem with two release dates and an optimal algorithm for a very practical special case of the problem.

MSC:

90B35 Deterministic scheduling theory in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahmadi R, Bagchi U (1990) Scheduling of multi-job customer orders in multi-machine environments. ORSA/TIMS Philadelphia
[2] Fan B, Cheng T (2016) Two-agent scheduling in a flowshop. Eur J Oper Res 252:376-384 · Zbl 1346.90342 · doi:10.1016/j.ejor.2016.01.009
[3] Garey M, Johnson D (1979) Computers and intractability: a guide to the theory of NP-completeness. Freeman, San Francisco · Zbl 0411.68039
[4] Hall L (1994) A polynomial approximation scheme for a constrained flow-shop scheduling problem. Math Oper Res 19(1):68-85 · Zbl 0821.90066 · doi:10.1287/moor.19.1.68
[5] Johnson S (1954) Optimal two- and three-stage production schedules with setup times included. Nav Res Logist Q 1:61-68 · Zbl 1349.90359 · doi:10.1002/nav.3800010110
[6] Jia Y, Guo R (2013) Optimal management of hospital physical examination process. Chin Med Rec 14(3):27-28
[7] Kashyrskikh K, Potts C, Sevastianoy S (2001) A 3/2-approximation algorithm for two-machine flow-shop sequencing subject to release dates. Discrete Appl Math 114:255-271 · Zbl 1168.90449 · doi:10.1016/S0166-218X(00)00374-7
[8] Lee C (1997) Minimizing the makespan in the two-machine flowshop scheduling problem with an availability constraint. Oper Res Lett 20:129-139 · Zbl 0882.90069 · doi:10.1016/S0167-6377(96)00041-7
[9] Lin B, Cheng T (2011) Scheduling with centralized and decentralized batching policies in concurrent open shops. Nav Res Logist 58:17-27 · Zbl 1210.90091 · doi:10.1002/nav.20437
[10] Lee C, Cheng T, Lin B (1993) Minimizing the makespan in three-machine assembly type flow shop problem. Manag Sci 39:616-625 · Zbl 0783.90054 · doi:10.1287/mnsc.39.5.616
[11] Leung J, Li H, Pinedo M (2006) Scheduling orders for multiple product types with duedate related objectives. Eur J Oper Res 168:370-389 · Zbl 1099.90541 · doi:10.1016/j.ejor.2004.03.030
[12] Lenstra J, Rinnooy Kan A, Brucker P (1977) Complexity of machine scheduling problems. Ann Discrete Math 1:343-362 · Zbl 0353.68067 · doi:10.1016/S0167-5060(08)70743-X
[13] Ng C, Cheng T, Yuan J (2003) Concurrent open shop scheduling to minimize the weighted number of tardy jobs. J Sched 6:405-412 · Zbl 1027.90033 · doi:10.1023/A:1024284828374
[14] Pan J, Shan J, Li G, Wu Z (2016) Report on urban development of China No.9: the road to healthy city. Social Sciences Academic Press, China
[15] Potts C (1985) Analysis of heuristics for two-machine flow-shop sequencing subject to release dates. Math Oper Res 10(4):576-584 · Zbl 0582.90055 · doi:10.1287/moor.10.4.576
[16] Potts C, Sevastyanov S, Strusevich V, Van Wassenhove L, Zwaneveld C (1995) The two-stage assembly scheduling problem: complexity and approximation. Oper Res 43:346-355 · Zbl 0837.90069 · doi:10.1287/opre.43.2.346
[17] Su Q, Yao X, Jiang Z, Zhang G (2006) Process reengineering and information system design for physical examination center. IFAC Proc 39(3):689-693 · doi:10.3182/20060517-3-FR-2903.00349
[18] Wang D, Liu F, Yin Y, Wang J, Wang Y (2015) Prioritized surgery scheduling in face of surgeon tiredness and fixed off-duty period. J Comb Optim 30(4):967-981 · Zbl 1327.90076 · doi:10.1007/s10878-015-9846-1
[19] Yang J (2011) Customer order scheduling in a two machine flowshop. Int J Manag Sci 17:95-116
[20] Yan Y, Wang Y, Zheng W, Xu J (2016) Construction of physical examination self service information management system and its application effect. Hosp Admin J PLA 23(4):336-338
[21] Zhong L, Luo S, Wu L, Xu L, Yang J, Tang G (2014) A two-stage approach for surgery scheduling. J Comb Optim 27(3):545-556 · Zbl 1297.90064 · doi:10.1007/s10878-012-9535-2
[22] Zhang X, Wang H, Wang X (2015) Patients scheduling problems with deferred deteriorated functions. J Comb Optim 30(4):1027-1041 · Zbl 1330.90039 · doi:10.1007/s10878-015-9852-3
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.