AI Chat Paper
Discover the SciOpen Platform and Achieve Your Research Goals with Ease.
Search articles, authors, keywords, DOl and etc.
{{expandStatus?'Exit ':''}}Advanced Search
We study scheduling problems with rejection on parallel-machine. Each job consists of a processing time, a rejection cost, and a release date. The goal is to minimize the makespan of the jobs accepted when the total rejection cost is not larger than a given threshold. Firstly, we verify that these problems are NP-hard. Secondly, for the multiprocessor scheduling problem with rejection, we give a pseudo-polynomial algorithm and two fully polynomial approximation schemes (FPTAS for short) for fixed positive integer m, where m is the number of machines. For the scheduling problem with rejection and the job with non-identical release time on m machines, we also design a pseudo-polynomial algorithm and a fully polynomial approximation scheme when m is a fixed positive integer. We provide an approximation algorithm with the worst case performance 2 for arbitrary positive integer m. Finally, we discuss the online scheduling problem with rejection. We show that even if there are just two distinct arrive times for the jobs, there is not any online algorithm whose competitive ratio is constant for it.
X. Tang, S. Bi, and Y. J. A. Zhang, Distributed routing and charging scheduling optimization for internet of electric vehicles, IEEE Internet of Things J., vol. 6, no. 1, pp. 136–148, 2019.
M. Sajid, H. Mittal, S. Pare, and M. Prasad, Routing and scheduling optimization for UAV assisted delivery system: A hybrid approach, Appl. Soft Comput., vol. 126, p. 109225, 2022.
H. Atabakhsh, A survey of constraint based scheduling systems using an artificial intelligence approach, Artif. Intell. Eng., vol. 6, no. 2, pp. 58–73, 1991.
K. Ecker, J. N. D. Gupta, and G. Schmidt, A framework for decision support systems for scheduling problems, Eur. J. Oper. Res., vol. 101, no. 3, pp. 452–462, 1997.
R. L. Graham, E. L. Lawler, J. K. Lenstra, and A. H. G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: A survey, Ann. Disc. Math., vol. 5, pp. 287–326, 1979.
Y. Bartal, S. Leonardi, A. Marchetti-Spaccamela, J. Sgall, and L. Stougie, Multiprocessor scheduling with rejection, SIAM Journal on Discrete Maths., vol. 13, no. 1, pp. 64–78, 2000.
D. W. Engels, D. R. Karger, S. G. Kolliopoulos, S. Sengupta, R. N. Uma, and J. Wein, Techniques for scheduling with rejection, J. Algorithms, vol. 49, no. 1, pp. 175–191, 2003.
H. Hoogeveen, M. Skutella, and G. J. Woeginger, Preemptive scheduling with rejection, Math. Program., vol. 94, pp. 361–374, 2003.
L. Zhang, L. Lu, and J. Yuan, Single-machine scheduling under the job rejection constraint, Theor. Comput. Sci., vol. 411, pp. 1877–1882, 2010.
W. Li, J. Li, X. Zhang, and Z. Chen, Penalty cost constrained identical parallel machine scheduling problem, Theor. Comput. Sci., vol. 607, pp. 181–192, 2015.
J. Ou, X. Zhong, and G. Wang, An improved heuristic for parallel machine scheduling with rejection, Eur. J. Oper. Res., vol. 241, no. 3, pp. 653–661, 2015.
L. Zhang and L. Lu, Parallel-machine scheduling with release dates and rejection, 4OR-Q. J. Oper. Res., vol. 14, no. 2, pp. 165–172, 2016.
X. Zhong and J. Ou, Parallel machine scheduling with restricted job rejection, Theor. Comput. Sci., vol. 690, pp. 1–11, 2017.
P. Liu and X. Lu, New approximation algorithms for machine scheduling with rejection on single and parallel machine, J. Comb. Optim., vol. 40, no. 4, pp. 929–952, 2020.
Y. He and X. Min, Online uniform machine scheduling with rejection, Computing, vol. 65, pp. 1–12, 2000.
S. S. Seiden, Preemptive multiprocessor scheduling with rejection, Theor. Comput. Sci., vol. 262, pp. 437–458, 2001.
L. Epstein, J. Noga, and G. J. Woeginger, Online scheduling of unit time jobs with rejection: Minimizing the total completion time, Oper. Res. Lett., vol. 30, no. 6, pp. 415–420, 2002.
C. Miao and Y. Zhang, Online scheduling with rejection on identical parallel machines, J. Syst. Sci. Complex., vol. 19, pp. 431–435, 2006.
Z. Cao and Y. Zhang, Scheduling with rejection and non-identical job arrivals, J. Syst. Sci. Complex., vol. 20, no. 4, pp. 529–535, 2007.
L. Lu, C. T. Ng, and L. Zhang, Optimal algorithms for single-machine scheduling with rejection to minimize the makespan, Int. J. Prod. Econ., vol. 130, no. 2, pp. 153–158, 2011.
R. Ma and S. Guo, Applying “peeling onion” approach for competitive analysis in online scheduling with rejection, Eur. J. Oper. Res., vol. 290, no. 1, pp. 57–67, 2021.
E. L. Lawler, Optimal sequencing a single machine subject to precedence constraints, Manag. Sci., vol. 19, no. 5, pp. 544–546, 1973.
104
Views
17
Downloads
0
Crossref
0
Web of Science
0
Scopus
0
CSCD
Altmetrics
The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).
京公网安备11010802044758号