Scheduling jobs with equal processing times and a single server on parallel identical machines. (English) Zbl 1353.90069
Summary: This paper studies the parallel-machine scheduling problem with a single server. There is a set of jobs to be processed on a set of \(m\) parallel and identical machines. Prior to processing on a machine, each job has to be loaded by a single server, which takes both the server and the machine a certain time. Preemption is not allowed. We consider the objective of minimizing the sum of jobs’ completion times. This problem has been shown to be NP-hard even when all jobs have equal processing times [P. Brucker et al., J. Sched. 5, No. 6, 429–457 (2002; Zbl 1040.90016)]. We prove in this paper that the SPT algorithm has a worst case ratio of \(1 + \frac{\sqrt{m - 1}}{\sqrt{m} + \sqrt{m - 1}} < 1.5\) for the equal-processing-time problem.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
Citations:
Zbl 1040.90016References:
| [1] | Allahverdi, A.; Ng, C. T.; Cheng, T. C.E.; Kovalyov, M. Y., A survey of scheduling problems with setup times or costs, European J. Oper. Res., 187, 985-1032 (2008) · Zbl 1137.90474 |
| [2] | Brucker, P.; Dhaenens-Flipo, C.; Knust, S.; Kravchenko, S. A.; Werner, F., Complexity results for parallel machine problems with a single server, J. Sched., 5, 429-457 (2002) · Zbl 1040.90016 |
| [3] | Brucker, P.; Knust, S.; Wang, G., Complexity results for flow-shop problems with a single server, European J. Oper. Res., 165, 398-407 (2005) · Zbl 1066.90024 |
| [4] | Cheng, T. C.E.; Kovalyov, M. Y., Scheduling a single server in a two-machine flow shop, Computing, 70, 167-180 (2003) · Zbl 1239.90047 |
| [5] | Glass, C. A.; Shafransky, Y. M.; Strusevich, V. A., Scheduling for parallel dedicated machines with a single server, Nav. Res. Logist., 47, 304-328 (2000) · Zbl 0968.90036 |
| [6] | Hall, N. G.; Potts, C. N.; Sriskandarajah, C., Parallel machine scheduling with a common server, Discrete Appl. Math., 102, 223-243 (2000) · Zbl 0972.90031 |
| [7] | Hasani, K.; Kravchenko, S. A.; Werner, F., Minimizing total weighted completion time approximately for the parallel machine problem with a single server, Inform. Process. Lett., 114, 500-503 (2014) · Zbl 1296.90047 |
| [8] | Jiang, Y.; Zhang, Q.; Hu, J.; Dong, J.; Ji, M., Single-server parallel-machine scheduling with loading and unloading times, J. Comb. Optim., 30, 201-213 (2015) · Zbl 1319.90032 |
| [9] | Kravchenko, S. A.; Werner, F., Parallel machine scheduling problems with a single server, Math. Comput. Modelling, 26, 1-11 (1997) · Zbl 1185.90082 |
| [10] | Kravchenko, S. A.; Werner, F., A heuristic algorithm for minimizing mean flow time with unit setups, Inform. Process. Lett., 79, 291-296 (2001) · Zbl 1032.68026 |
| [11] | Ou, J. W.; Qi, X. T.; Lee, C.-Y., Parallel machine scheduling with multiple unloading servers, J. Sched., 13, 213-226 (2010) · Zbl 1193.90108 |
| [12] | Shi, L.; Cheng, X. G., On a two-machine flow-shop scheduling problem with a single server and unit processing times, J. Appl. Math. Bioinform., 1, 2, 33-38 (2011) · Zbl 1254.90071 |
| [13] | Shi, L.; Cheng, X. G., Minimizing total completion time in a two-machine flow-shop scheduling problems with a single server, J. Math. Comput. Sci., 2, 3, 435-440 (2012) |
| [14] | Wang, G.; Cheng, T. C.E., An approximation algorithm for parallel machine scheduling with a common server, J. Oper. Res. Soc. Japan, 52, 234-237 (2001) · Zbl 1131.90364 |
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.
