On the parameterized tractability of single machine scheduling with rejection. (English) Zbl 1403.90332
Summary: In this paper, we study a single machine scheduling problem with rejection. In such a scheduling problem, the scheduler can reject to process a job in the shop at a certain cost. Our objective is to minimize the total completion time of the jobs to be processed in the shop, given that the total rejection cost will not exceed a certain predefined threshold. The problem is known to be NP-hard, and to better investigate its hardness our objective is to study whether the problem becomes tractable when some specific natural parameters are of a limited size. The analysis is done by using the theory of parameterized complexity and includes the following parameters: the cardinality of the set of accepted jobs, the number of different processing times, the number of different rejection costs, the maximal processing time, and the maximal rejection cost. We show that the problem is W[1]-hard for the first parameter, while it is fixed-parameterized tractable for all other parameters.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
Keywords:
single machine scheduling; scheduling with rejection; parameterized complexity; fixed-parameter tractabilityReferences:
| [1] | van Bevern, R.; Mnich, M.; Niedermeier, R.; Weller, M., Interval scheduling and colorful independent sets, Journal of Scheduling, 18, 5, 449-469, (2015) · Zbl 1328.90065 |
| [2] | van Bevern, R.; Niedermeier, R.; Suchý, O., A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack, Journal of Scheduling, 20, 3, 255-265, (2017) · Zbl 1376.90028 |
| [3] | Bredereck, R.; Faliszewski, P.; Niedermeier, R.; Skowron, P.; Talmon, N., Mixed integer programming with convex/concave constraints: fixed-parameter tractability and applications to multicovering and voting, arXiv preprint arXiv:1709.02850, (2017) |
| [4] | Cygan, M.; Fomin, F.; Kowalik, L.; Lokshtanov, D.; Marx, D.; Pilipczuk, M.; Pilipczuk, M., Parameterized algorithms, (2015), Springer · Zbl 1334.90001 |
| [5] | Dadush, D.; Peikert, C.; Vempala, S., Enumerative lattice algorithms in any norm via m-ellipsoid coverings, Proceedings of the 52nd annual symposium on foundations of computer science (focs 2011), 580-589, (2011) · Zbl 1292.68091 |
| [6] | Downey, R.; Fellows, M., Fixed-parameter intractability, Proceedings of the 7th annual structure in complexity theory conference (coco ’92), 36-49, (1992) |
| [7] | Downey, R.; Fellows, M., Parameterized complexity, (1999), Springer |
| [8] | Ehrgott, M., Multicriteria optimization, (2005), Springer · Zbl 1132.90001 |
| [9] | Flum, J.; Grohe, M., Parameterized Complexity Theory, (1998), Springer |
| [10] | Graham, R.; Lawler, E.; Lenstra, J.; Kan, A., Optimization and approximation in deterministic sequencing and scheduling: a survey, Annals of Discrete Mathematics, 3, 287-326, (1979) · Zbl 0411.90044 |
| [11] | Grötschel, M.; Lovasz, L.; Schrijver, A., Geometric algorithms and combinatorial optimization, algorithms and combinatorics: study and research texts, (1988), Springer-Verlag · Zbl 0634.05001 |
| [12] | Hermelin, D.; Karhi, S.; Pinedo, M.; Shabtay, D., New algorithms for minimizing the weighted number of tardy jobs on a single machine, Annals of Operations Research, (2018) |
| [13] | Hermelin, D., Kubitza, J., Shabtay, D., Talmon, N., & Woeginger, G. Scheduling two competing agents when one agent has significantly fewer jobs. In Proceedings of the 10th international symposium on parameterized and exact computation (ipec ’15) (pp. 55-65).; Hermelin, D., Kubitza, J., Shabtay, D., Talmon, N., & Woeginger, G. Scheduling two competing agents when one agent has significantly fewer jobs. In Proceedings of the 10th international symposium on parameterized and exact computation (ipec ’15) (pp. 55-65). · Zbl 1378.68021 |
| [14] | Knop, D.; Koutecký, M., Scheduling meets n-fold integer programming, Journal of Scheduling, (2018) · Zbl 1418.90113 |
| [15] | Mnich, M.; van Bevern, R., Parameterized complexity of machine scheduling: 15 open problems, Computers and Operations Research, (2018), In Press · Zbl 1458.90333 |
| [16] | Mnich, M.; Wiese, A., Scheduling and fixed-parameter tractability, Mathematical Programming, 154, 1-2, 533-562, (2015) · Zbl 1332.68089 |
| [17] | Niedermeier, R., Invitation to fixed-parameter algorithms, (2006), Oxford University Press · Zbl 1095.68038 |
| [18] | Oertel, T.; Wagner, C.; Weismantel, R., Integer convex minimization by mixed integer linear optimization, Operations Research Letters, 43, 6-7, 379-488, (2014) |
| [19] | Shabtay, D.; Gaspar, N.; Kaspi, M., A survey on offline scheduling with rejection, Journal of Scheduling, 16, 1, 3-28, (2013) · Zbl 1297.90058 |
| [20] | 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, 4, 395-424, (2012) · Zbl 1244.90102 |
| [21] | Slotnick, S. A., Order acceptance and scheduling: A taxonomy and review, European Journal of Operational Research, 212, 1, 1-11, (2011) |
| [22] | Smith, W., Various optimizers for single-stage production, Naval Research Logistics, 3, 59-66, (1956) |
| [23] | T’kindt, V.; Billaut, J.-C.; Scott, H., Multicriteria scheduling: theory, models and algorithms, (2011), Springer |
| [24] | Zhang, L. Q.; Lu, L. F.; Yuan, J. J., Single-machine scheduling under the job rejection constraint, Theoretical Computer Science, 411, 16-18, 1877-1882, (2010) · Zbl 1192.68111 |
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.
