Scheduling with multiple servers. (English. Russian original) Zbl 1218.93058
Autom. Remote Control 71, No. 10, 2109-2121 (2010); translation from Avtom. Telemekh. 2010, No. 10, 107-121 (2010).
Summary: We consider the scheduling a set of jobs on a set of identical parallel machines. Before the processing of a job can start, a setup is required which has to be performed by a given set of servers. We consider the complexity of such problems for the minimization of the makespan. For the problem with equal processing times and equal setup times we give a polynomial algorithm. For the problem with unit setup times, \(m\) machines and \(m-1\) servers, we develop a pseudopolynomial algorithm. However, the problem with fixed numbers of machines and servers in the case of minimizing maximum lateness is proven to be unary NP-hard. In addition, recent algorithms for some parallel machine scheduling problems with constant processing times are generalized to the corresponding server problems for the case of constant setup times. Moreover, we perform a worst case analysis of two list scheduling algorithms for makespan minimization.
MSC:
| 93C83 | Control/observation systems involving computers (process control, etc.) |
| 90B35 | Deterministic scheduling theory in operations research |
Keywords:
scheduling of jobs; identical parallel machines; complexity; minimization of the makespan; worst case analysisReferences:
| [1] | Hall, N.G., Potts, C.N., and Sriskandarajah, C., Parallel Machine Scheduling with a Common Server, Discret. Appl. Math., 2000, vol. 102, pp. 223–243. · Zbl 0972.90031 · doi:10.1016/S0166-218X(99)00206-1 |
| [2] | Koulamas, C.P., Scheduling on Two Parallel Machines for Minimizing Machine Interference, Working Paper, 1993. |
| [3] | Koulamas, C.P. and Smith, M.L., Look-ahead Scheduling for Minimizing Machine Interference, Int. J. Product. Res., 1988, vol. 26, pp. 1523–1533. · doi:10.1080/00207548808947963 |
| [4] | Kravchenko, S.A. and Werner, F., Parallel Machine Scheduling Problems with a Single Server, Math. Comput. Model., 1997, vol. 26, pp. 1–11. · Zbl 1185.90082 · doi:10.1016/S0895-7177(97)00236-7 |
| [5] | Brucker, P., Dhaenens-Flipo, C., Knust, S., Kravchenko, S.A., and Werner, F., Complexity Results for Parallel Machine Problems with a Single Server, J. Schedul., 2002, vol. 5, pp. 429–457. · Zbl 1040.90016 · doi:10.1002/jos.120 |
| [6] | Allahverdi, A., Ng, C.T., Cheng, T.C.E., and Kovalyov, M.Y., A Survey of Scheduling Problems with Setup Times or Costs, Eur. J. Oper. Res., 2008, vol. 187, pp. 985–1032. · Zbl 1137.90474 · doi:10.1016/j.ejor.2006.06.060 |
| [7] | Ou, J., Qi, X., and Lee, C.-Y., ParallelMachine Scheduling withMultiple Unloading Servers, J. Schedul., 2009, vol. 13, no. 3, pp. 213–226. · Zbl 1193.90108 · doi:10.1007/s10951-009-0104-1 |
| [8] | Huang, S., Cai, L., and Zhang, X., Parallel Dedicated Machine Scheduling Problem with Sequencedependent Setups and a Single Server, Comput. & Indust. Eng., 2010, vol. 58, no. 1, pp. 165–174. · doi:10.1016/j.cie.2009.10.003 |
| [9] | Aronson, J.E., Two Heuristics for the Deterministic, Single Operator, Multiple Machine, Multiple Run Cyclic Scheduling Problem, J. Oper. Manage., 1984, vol. 4, pp. 159–773. · doi:10.1016/0272-6963(84)90030-5 |
| [10] | Wilhelm, W.E. and Sarin, S.C., A Structure for Sequencing Robot Activities in Machine Loading Applications, Int. J. Product. Res., 1985, vol. 23, pp. 47–64. · doi:10.1080/00207548508904690 |
| [11] | Hall, N.G., Kamoun, H., and Sriskandarajah, C., Scheduling in Robotic Cells: Classification, Two and Three Machine Cells, Oper. Res., 1997, vol. 45, pp. 421–439. · Zbl 0891.90080 · doi:10.1287/opre.45.3.421 |
| [12] | Hall, N.G., Kamoun, H., and Sriskandarajah, C., Scheduling in Robotic Cells, Complexity and Sready State Analysis, Eur. J. Oper. Res., 1998, vol. 109, pp. 43–65. · Zbl 0949.90041 · doi:10.1016/S0377-2217(96)00333-5 |
| [13] | Kamoun, H., Hall, N.G., and Sriskandarajah, C., Scheduling in Robotic Cells: Heuristics and Cell Design, Oper. Res., 1999, vol. 47, pp. 821–835. · Zbl 1009.90049 · doi:10.1287/opre.47.6.821 |
| [14] | Ganesharajah, T., Hall, N.G., and Sriskandarajah, C., Design and Operational Issues in AGV-served Manufacturing Systems, Ann. Oper. Res., 1998, vol. 76, pp. 109–154. · Zbl 0896.90083 · doi:10.1023/A:1018936219150 |
| [15] | Sethi, S.P., Sriskandarajah, C., Sorger, G., Blazewicz, J., and Kubiak, W., Sequencing of Parts and Robot Moves in a Robotic Cell, Int. J. Flexible Manufactur. Syst., 1992, vol. 4, pp. 331–358. · doi:10.1007/BF01324886 |
| [16] | Dobson, G. and Kamarkar, U.S., Simultaneous Resource Scheduling to Minimize Weighted Flow Time, Oper. Res., 1988, vol. 37, pp. 1523–1533. |
| [17] | Sahney, V.K., Single-server, Two-machine Sequencing with Switching Time, Oper. Res., 1972, vol. 20, pp. 24–26. · Zbl 0238.90033 · doi:10.1287/opre.20.1.24 |
| [18] | Graham, R.L., Lawler, E.L., Lenstra, J.K., and Rinnooy Kan, A.H.G., Optimization and Approximation in Deterministic Machine Scheduling: A Survey, Ann. Discret. Math., 1979, vol. 5, pp. 287–326. · Zbl 0411.90044 · doi:10.1016/S0167-5060(08)70356-X |
| [19] | Hall, N.G., Potts, C.N., and Sriskandarajah, C., Parallel Machine Scheduling with a Common Server, in The Fifth International Workshop on Project Management and Scheduling, Abstracts, 1997, pp. 102–106. · Zbl 0972.90031 |
| [20] | Tanaev, V.S., Gordon, V.S., and Shafransky, Y.M., Scheduling Theory, Single-Stage Systems, Dordrecht: Kluwer, 1994. |
| [21] | Brucker, P. and Kravchenko, S.A., Scheduling Jobs with Equal Processing Times and Time Windows on Identical Parallel Machines, J. Schedul., 2008, vol. 11, pp. 229–237. · Zbl 1168.90426 · doi:10.1007/s10951-008-0063-y |
| [22] | Kravchenko, S.A. and Werner, F., On a Parallel Machine Scheduling Problem with Equal Processing Times, Discret. Appl. Math., 2009, vol. 157, pp. 848–852. · Zbl 1186.68068 · doi:10.1016/j.dam.2008.09.003 |
| [23] | Kravchenko, S.A. and Werner, F., On a Parallel Machine Scheduling Problem with Equal Processing Times, Preprint of Otto-von-Guericke-Universität, Magdeburg, 2007, no. 26/07. |
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.
