<abstract xmlns="http://www.w3.org/1999/xhtml">

<p>In this paper, we study eight single-machine scheduling problems with rejection and position-dependent parameters. We consider two position-dependent parameters as follows: (1) position-dependent weights and (2) position-dependent processing times. In addition, we also introduce a weight-modifying activity or a rate-modifying activity into our problems. In the first six problems, the task is to minimize the sum of the total weighted completion time of accepted jobs and the total rejection cost of rejected jobs. We show that all six problems can be solved in polynomial time. In the last two problems, the task is to minimize the total weighted completion time of accepted jobs under the constraint that the total rejection cost of rejected jobs can not exceed a given upper bound. We show that these two problems are binary NP-hard and each problem admits an FPTAS.</p>
</abstract>

In this paper, we study eight single-machine scheduling problems with rejection and position-dependent parameters. We consider two position-dependent parameters as follows: (1) position-dependent weights and (2) position-dependent processing times. In addition, we also introduce a weight-modifying activity or a rate-modifying activity into our problems. In the first six problems, the task is to minimize the sum of the total weighted completion time of accepted jobs and the total rejection cost of rejected jobs. We show that all six problems can be solved in polynomial time. In the last two problems, the task is to minimize the total weighted completion time of accepted jobs under the constraint that the total rejection cost of rejected jobs can not exceed a given upper bound. We show that these two problems are binary NP-hard and each problem admits an FPTAS.

New Results on Single-Machine Scheduling with Rejection to Minimize the Total Weighted Completion Time

Foundations of Computing and Decision Sciences

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

In this paper, we study eight single-machine scheduling problems with rejection and position-dependent parameters. We consider two position-dependent...

New Results on Single-Machine Scheduling with Rejection to Minimize the Total Weighted Completion Time

Publié en ligne: 16 févr. 2024

Pages: 75 - 94

Reçu: 19 févr. 2023

Accepté: 12 sept. 2023

DOI: https://doi.org/10.2478/fcds-2024-0006

Mots clés
Scheduling with rejection, position-dependent parameters, dynamic programming

© 2024 Liqi Zhang et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

New Results on Single-Machine Scheduling with Rejection to Minimize the Total Weighted Completion Time

Publié en ligne: 16 févr. 2024

Pages: 75 - 94

Reçu: 19 févr. 2023

Accepté: 12 sept. 2023

DOI: https://doi.org/10.2478/fcds-2024-0006

Mots clésScheduling with rejection, position-dependent parameters, dynamic programming

© 2024 Liqi Zhang et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Mots clés
Scheduling with rejection, position-dependent parameters, dynamic programming