nach oben

Journal of Scheduling

Erschienen in:

20.07.2018

The single-processor scheduling problem with time restrictions: complexity and related problems

verfasst von: Rachid Benmansour, Oliver Braun, Saïd Hanafi

Erschienen in: Journal of Scheduling | Ausgabe 4/2019

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We consider the single-processor scheduling problem with time restrictions (STR) in order to minimize the makespan, where a set of independent jobs has to be processed on a single processor, subject only to the following constraint: During any time period of length \(\alpha \), the number of jobs being executed is less than or equal to a given integer value B. First, we prove that the STR problem is binary NP-hard even for \(B=2\) by pointing out an interesting analogy of this problem to the parallel machine scheduling problem with a single server with equal processing times. Next, we give a formal description of the STR problem by providing two mixed integer programming formulations to solve it optimally. The first is based on time-indexed variables and the second is based on assignment and positional date variables (APV). Both models were tested on randomly generated instances, and the experimental results show that the APV model performs very well and can solve problem instances of up to \(n=500\) jobs.

Vorheriger Artikel Unbounded parallel-batch scheduling with drop-line tasks

Nächster Artikel Quality of strong equilibria for selfish bin packing with uniform cost sharing

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Abdekhodaee, A. H., & Wirth, A. (2002). Scheduling parallel machines with a single server: Some solvable cases and heuristics. Computers & Operations Research, 29, 295–315.CrossRef

Balas, E. (1985). On the facial structure of scheduling polyhedra. In R. W. Cottle (Ed.), Mathematical programming essays in honor of George B. Dantzig Part I. Mathematical Programming Studies (Vol. 24, pp. 179–218). Berlin, Heidelberg: Springer.

Benmansour, R., Braun, O., & Allaoui, H. (2015). Modeling the single-processor scheduling problem with time restrictions as a parallel machine scheduling problem. In 7th multidisciplinary international conference on scheduling: Theory and applications (MISTA) (pp. 325–330).

Benmansour, R., Braun, O., & Artiba, A. (2014). On the single-processor scheduling problem with time restrictions. In International conference on control, decision and information technologies (CoDIT) (pp. 242–245).

Blazewicz, J., Ecker, K. H., Pesch, E., Schmidt, G., & Weglarz, J. (2007). Handbook on scheduling: From theory to applications. Berlin: Springer.

Braun, O., Chung, F., & Graham, R. (2014). Single-processor scheduling with time restrictions. Journal of Scheduling, 17, 399–403.CrossRef

Braun, O., Chung, F., & Graham, R. (2016). Worst-case analysis of the LPT algorithm for single processor scheduling with time restrictions. OR Spectrum, 38, 531–540.CrossRef

Brucker, P., Dhaenens-Flipo, C., Knust, S., Kravchenko, S. A., & Werner, F. (2002). Complexity results for parallel machine problems with a single server. Journal of Scheduling, 5, 429–457.CrossRef

Chen, B., Potts, C. N., & Woeginger, G. J. (1998). A review of machine scheduling: Complexity, algorithms and approximability. In D. Z. Du & P. M. Pardalos (Eds.), Handbook of combinatorial optimization (pp. 1493–1641). Boston, MA: Springer.CrossRef

Dyer, M. E., & Wolsey, L. A. (1990). Formulating the single machine sequencing problem with release dates as a mixed integer program. Discrete Applied Mathematics, 26, 255–270.CrossRef

Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: A guide to the theory of NP-completeness. New York: W. H. Freeman & Co.

Garey, M. R., Tarjan, R. E., & Wilfong, G. T. (1988). One-processor scheduling with symmetric earliness and tardiness penalties. Mathematics of Operations Research, 13(2), 330–348.CrossRef

Glass, C. A., Shafransky, Y. M., & Strusevich, V. A. (2000). Scheduling for parallel dedicated machines with a single server. Naval Research Logistics, 47, 304–328.CrossRef

Hall, N. G., Potts, C. N., & Sriskandarajah, C. (2000). Parallel machine scheduling with a common server. Discrete Applied Mathematics, 102, 223–243.CrossRef

Hoogeveen, H., & van de Velde S. (1995). Formulating a scheduling problem with almost identical jobs by using positional completion times. In Proceedings of the international conference on integer programming and combinatorial optimization (pp. 292–306). Springer.

Keha, A., Khowala, K., & Fowler, J. (2009). Mixed integer programming formulations for single machine scheduling problems. Computers & Industrial Engineering, 56, 357–367.CrossRef

Kim, M. Y., & Lee, Y. H. (2012). MIP models and hybrid algorithm for minimizing the makespan of parallel machines scheduling problem with a single server. Computers & Operations Research, 39, 2457–2468.CrossRef

Kravchenko, S. A., & Werner, F. (1997). Parallel machine scheduling problems with a single server. Mathematical and Computer Modelling, 26, 1–11.CrossRef

Lasserre, J. B., & Queyranne, M. (1992). Generic scheduling polyhedral and a new mixed-integer formulation for single-machine scheduling. In Proceedings of the 2nd IPCO conference (pp. 136149). Pittsburgh: Carnegie-Mellon University.

Lawler, E. L., Lenstra, J. K., Kan, A. H. G. R., & Shmoys, D. B. (1993). Sequencing and scheduling: Algorithms and complexity. Handbooks in Operations Research and Management Science, 4, 445–522.CrossRef

Leung, J. Y. (2004). Handbook of scheduling: Algorithms, models, and performance analysis. Boca Raton: CRC Press.

Mokotoff, E. (2001). Parallel machine scheduling problems: A survey. Asia-Pacific Journal of Operational Research, 18, 193–242.

Pinedo, M. L. (2016). Scheduling: Theory, algorithms, and systems. Berlin: Springer.CrossRef

Queyranne, M., & Schulz, A. S. (1994). Polyhedral approaches to machine scheduling. Technical Report, TU Berlin, Preprint 408/1994.

Sourd, F. (2009). New exact algorithms for one-machine earliness–tardiness scheduling. INFORMS Journal on Computing, 21, 167–175.CrossRef

Sousa, J. P., & Wolsey, L. A. (1992). A time indexed formulation of non-preemptive single machine scheduling problems. Mathematical Programming, 54, 353–367.CrossRef

Unlu, Y., & Mason, S. J. (2010). Evaluation of mixed integer programming formulations for non-preemptive parallel machine scheduling problems. Computers & Industrial Engineering, 58, 785–800.CrossRef

Van den Akker, J. M., Hurkens, C. A., & Savelsbergh, M. W. (2000). Time-indexed formulations for machine scheduling problems: Column generation. INFORMS Journal on Computing, 12(2), 111–124.CrossRef

Zhang, A., Chen, Y., Chen, L., & Chen, G. (2017). On the NP-hardness of scheduling with time restrictions. CoRR. arXiv:1703.00575.

Zhang, A., Ye, F., Chen, Y., & Chen, G. (2017). Better permutations for the single-processor scheduling with time restrictions. Optimization Letters, 11(4), 715–724.CrossRef

Titel: The single-processor scheduling problem with time restrictions: complexity and related problems
verfasst von: Rachid Benmansour
Oliver Braun
Saïd Hanafi
Publikationsdatum: 20.07.2018
Verlag: Springer US
Erschienen in: Journal of Scheduling / Ausgabe 4/2019
Print ISSN: 1094-6136
Elektronische ISSN: 1099-1425
DOI: https://doi.org/10.1007/s10951-018-0579-8

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 4/2019

Quality of strong equilibria for selfish bin packing with uniform cost sharing

The evolution of schematic representations of flow shop scheduling problems

Parallel machine makespan minimization subject to machine availability and total completion time constraints

Malleable scheduling for flows of jobs and applications to MapReduce

Lower bounds for online bin covering-type problems

Preemptive parallel-machine scheduling problem of maximizing the number of on-time jobs

Premium Partner