Parallel-Machine Scheduling Problem under the Job Rejection Constraint
详细信息 查看全文
- 作者：Weidong Li (18)
Jianping Li (18)
Xuejie Zhang (18)
Zhibin Chen (19) - 关键词：Scheduling ; Rejection penalty ; Polynomial time approximation scheme ; Fully polynomial time approximation scheme
- 刊名：Lecture Notes in Computer Science
- 出版年：2014
- 出版时间：2014
- 年：2014
- 卷：8497
- 期：1
- 页码：158-169
- 参考文献：1. Alon, N., Azar, Y., Woeginger, G.J., Yadid, T.: Approximation schemes for scheduling on parallel machines. Journal of Scheduling?1, 55-6 (1998) CrossRef
2. Angel, E., Bampis, E., Kononov, A.: A FPTAS for approximating the unrelated parallel machines scheduling problem with costs. In: Meyer auf der Heide, F. (ed.) ESA 2001. LNCS, vol.?2161, pp. 194-05. Springer, Heidelberg (2001) CrossRef
3. Bartal, Y., Leonardi, S., Spaccamela, A.M., Sgall, J., Stougie, L.: Multiprocessor scheduling with rejection. SIAM Journal on Discrete Mathematics?13, 64-8 (2000) CrossRef
4. Cao, Z., Yang, X.: A PTAS for parallel batch scheduling with rejection and dynamic job arrivals. Theoretical Computer Science?410, 2732-745 (2009) CrossRef
5. Cao, Z., Zhang, Y.: Scheduling with rejection and non-identical job arrivals. Journal of Systems Science and Complexity?20, 529-35 (2007) CrossRef
6. Cheng, Y., Sun, S.: Scheduling linear deteriorating jobs with rejection on a single machine. European Journal of Operational Research?194, 18-7 (2009) CrossRef
7. Engels, D.W., Karger, D.R., Kolliopoulos, S.G., Sengupta, S., Uma, R.N., Wein, J.: Techniques for scheduling with rejection. Journal of Algorithms?49, 175-91 (2003) CrossRef
8. Graham, R.L.: Bounds for certain multiprocessing anomalies. Bell System Technical Journal?45, 1563-581 (1966) CrossRef
9. Hochbaum, D.S., Shmoys, D.B.: Using dual approximation algorithms for scheduling problems: theoretical and practical results. Journal of Association for Computing Machinery?34, 144-62 (1987) CrossRef
10. Hoogeveen, H., Skutella, M., Woeginger, G.J.: Preemptive scheduling with rejection. Mathematics Programming?94, 361-74 (2003) CrossRef
11. Horowitz, E., Sahni, S.: Exact and approximate algorithms for scheduling nonidentical processors. Journal of the ACM?23, 317-27 (1976) CrossRef
12. Jansen, K., Porkolab, L.: Improved approximation schemes for scheduling unrelated parallel machines. In: Proceedings of STOS 1999, 408- 417 (1999)
13. Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B.: Sequencing and scheduling: Algorithms and complexity. Handbooks in Operations Research and Management Science?4, 445-52 (1993) CrossRef
14. Lin, J.H., Vitter, J.S.: / ε-Approximation algorithms with minimum packing constraint violation. In: Proceedings of STOS 1992, pp. 771-82 (1992)
15. Lu, L., Zhang, L., Yuan, J.: The unbounded parallel batch machine scheduling with release dates and rejection to minimize makespan. Theoretical Computer Science?396, 283-89 (2008) CrossRef
16. Lu, L., Cheng, T.C.E., Yuan, J., Zhang, L.: Bounded single-machine parallel-batch scheduling with release dates and rejection. Computers & Operation Research?36, 2748-751 (2009) CrossRef
17. Lu, S., Feng, H., Li, X.: Minimizing the makespan on a single parallel batching machine. Theoretical Computer Science?411, 1140-145 (2010) CrossRef
18. Seiden, S.: Preemptive multiprocessor scheduling with rejection. Theoretical Computer Science?262, 437-58 (2001) CrossRef
19. Shabtay, D., Gaspar, N., Yedidsion, L.: A bicriteria approach to scheduling a single machine with job rejection and positional penalties. Journal of Combinatorial Optimization?23, 395-24 (2012) CrossRef
20. Shabtay, D., Gaspar, N., Kaspi, M.: A survey on offline scheduling with rejection. Journal of Scheduling?16, 3-8 (2013) CrossRef
21. Shmoys, D.B., Tardos, E.: An approximation algorithm for the generalized assignment problem. Mathematical Programming?62, 461-74 (1993) CrossRef
22. Zhang, L., Lu, L., Yuan, J.: Single machine scheduling with release dates and rejection. European Journal of Operational Research?198, 975-78 (2009) CrossRef
23. Zhang, L., Lu, L., Yuan, J.: Single-machine scheduling under the job rejection constraint. Theoretical Computer Science?411, 1877-882 (2010) CrossRef
24. Zhang, Y., Ren, J., Wang, C.: Scheduling with rejection to minimize the makespan. In: Du, D.-Z., Hu, X., Pardalos, P.M. (eds.) COCOA 2009. LNCS, vol.?5573, pp. 411-20. Springer, Heidelberg (2009) CrossRef - 作者单位：Weidong Li (18)
Jianping Li (18)
Xuejie Zhang (18)
Zhibin Chen (19)
18. Yunnan University, Kunming, 650091, P.R. China
19. Kunming University of Science and Technology, Kunming, 650500, P.R. China - ISSN：1611-3349
文摘
Given m identical machines and n independent jobs, each job J j has a processing time (or size) p j and a penalty e j . A job can be either rejected, in which case its penalty is paid, or scheduled on one of the machines, in which case its processing time contributes to the load of that machine. The objective is to minimize the makespan of the schedule for accepted jobs under the constraint that the total penalty of the rejected jobs is no more than a given bound B. In this paper, we present a 2-approximation algorithm within strongly polynomial time and a polynomial time approximation scheme whose running time is \(O(nm^{O(\frac{1}{\epsilon^2})}+mn^2)\) for the general case. Moreover, we present a fully polynomial time approximation scheme for the case where the number of machines is a fixed constant. This result improves previous best running time from O(n m--/ε m ) to O(1/ε 2m----em class="a-plus-plus">mn 2) .