Elisa Chinos, Nodari Vakhania, "Polynomially Solvable and NP-hard Special Cases for Scheduling with Heads and Tails," International Journal of Electrical Engineering and Computer Science, vol. 4, pp. 10-14, 2022, DOI:10.37394/232027.2022.4.2
Elisa Chinos, Nodari Vakhania. Polynomially Solvable and NP-hard Special Cases for Scheduling with Heads and Tails.
International Journal of Electrical Engineering and Computer Science. 2022;4:10-14. 10.37394/232027.2022.4.2
International Journal of Electrical Engineering and Computer Science
E-ISSN: 2769-2507
Volume 4, 2022
Polynomially Solvable and NP-hard Special Cases for Scheduling with Heads and Tails
Authors: ,
Abstract: We consider a basic single-machine scheduling problem when jobs have release and delivery times and the objective is to minimize maximum job lateness. This problem is known to be strongly NP-hard. We study inherent structure of this problem exploring its special cases and the conditions when the problem can be efficiently solved.
Pages: 10-14 DOI: 10.37394/232027.2022.4.2WSEAS Transactions on International Journal of Electrical Engineering and Computer Science, E-ISSN: 2769-2507, Volume 4, 2022, Art. #2
×
Citation Tools