An FPTAS for parallel-machine scheduling under a grade of service provision to minimize makespan. (English) Zbl 1191.68102
Summary: We consider the \(m\) parallel-machine scheduling problem that process service requests from various customers who are entitled to different levels of grade of service. The objective is to minimize the makespan. We give a fully polynomial-time approximation scheme for the case where \(m\) is fixed.
MSC:
| 68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
| 90B35 | Deterministic scheduling theory in operations research |
References:
| [1] | Graham, R. L.; Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Optimization and approximation in deterministic sequencing and scheduling: a survey, Annals of Discrete Mathematics, 5, 287-326 (1979) · Zbl 0411.90044 |
| [2] | Hwang, H. C.; Chang, S. Y.; Lee, K., Parallel machine scheduling under a grade of service provision, Computers & Operations Research, 31, 2055-2061 (2004) · Zbl 1074.68529 |
| [3] | Ji, M.; Cheng, T. C.E., An FPTAS for scheduling jobs with piecewise linear decreasing processing times to minimize makespan, Information Processing Letters, 102, 41-47 (2007) · Zbl 1184.68125 |
| [4] | Ji, M.; Cheng, T. C.E., Parallel-machine scheduling with simple linear deterioration to minimize total completion time, European Journal of Operational Research, 188, 342-347 (2008) · Zbl 1149.90343 |
| [5] | Jiang, Y. W., Online scheduling on parallel machines with two GoS levels, Lecture Notes in Computer Science, 4041, 11-21 (2006) · Zbl 1137.90493 |
| [6] | Jiang, Y. W.; He, Y.; Tang, C. M., Optimal online algorithms for scheduling on two identical machines under a grade of service, Journal of Zhejiang University—Science A, 7, 309-314 (2006) · Zbl 1108.90314 |
| [7] | Kovalyov, M. Y.; Kubiak, W., A fully polynomial approximation scheme for minimizing makespan of deteriorating jobs, Journal of Heuristics, 3, 287-297 (1998) · Zbl 0903.90100 |
| [8] | Kovalyov, M. Y.; Kubiak, W., A fully polynomial approximation scheme for the weighted earliness-tardiness problem, Operations Research, 47, 757-761 (1999) · Zbl 0976.90042 |
| [9] | Park, J.; Chang, S. Y.; Lee, K., Online and semi-online scheduling of two machines under a grade of service provision, Operations Research Letters, 34, 692-696 (2006) · Zbl 1112.90036 |
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.
