Document Open Access Logo

An FPTAS of Minimizing Total Weighted Completion Time on Single Machine with Position Constraint

Authors Gruia Calinescu, Florian Jaehn, Minming Li, Kai Wang

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2017.19.pdf
  • Filesize: 0.49 MB
  • 13 pages

Document Identifiers

Author Details

Gruia Calinescu
Florian Jaehn
Minming Li
Kai Wang

Cite As Get BibTex

Gruia Calinescu, Florian Jaehn, Minming Li, and Kai Wang. An FPTAS of Minimizing Total Weighted Completion Time on Single Machine with Position Constraint. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 19:1-19:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ISAAC.2017.19

Abstract

In this paper we study the classical scheduling problem of minimizing the total weighted completion time on a single machine with the constraint that one specific job must be scheduled at a specified position. We give dynamic programs with pseudo-polynomial running time, and a fully polynomial-time approximation scheme (FPTAS).

Subject Classification

Keywords
  • FPTAS
  • Scheduling
  • Approximation Algorithm

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Jacek Błażewicz, Paolo Dell'Olmo, Maciej Drozdowski, and Przemysław Mączka. Scheduling multiprocessor tasks on parallel processors with limited availability. European Journal of Operational Research, 149(2):377-389, 2003. Google Scholar
  2. Dirk Briskorn, Byung-Cheon Choi, Kangbok Lee, Joseph Leung, and Michael Pinedo. Complexity of single machine scheduling subject to nonnegative inventory constraints. European Journal of Operational Research, 207(2):605-619, 2010. Google Scholar
  3. Dirk Briskorn, Florian Jaehn, and Erwin Pesch. Exact algorithms for inventory constrained scheduling on a single machine. Journal of scheduling, 16(1):105-115, 2013. Google Scholar
  4. Dirk Briskorn and J YT Leung. Minimizing maximum lateness of jobs in inventory constrained scheduling. Journal of the Operational Research Society, 64(12):1851-1864, 2013. Google Scholar
  5. Dirk Briskorn and Erwin Pesch. Variable very large neighbourhood algorithms for truck sequencing at transshipment terminals. International Journal of Production Research, 51(23-24):7140-7155, 2013. Google Scholar
  6. Jen-Shiang Chen. Optimization models for the tool change scheduling problem. Omega, 36(5):888-894, 2008. Google Scholar
  7. A Costa, FA Cappadonna, and S Fichera. Minimizing the total completion time on a parallel machine system with tool changes. Computers &Industrial Engineering, 91:290-301, 2016. Google Scholar
  8. M Drozdowski, F Jaehn, and R Paszkowski. Scheduling position dependent maintenance operations. Operations Research, 2016. to appear. Google Scholar
  9. Péter Györgyi and Tamás Kis. Approximation schemes for single machine scheduling with non-renewable resource constraints. Journal of Scheduling, 17(2):135-144, 2014. Google Scholar
  10. Péter Györgyi and Tamás Kis. Approximability of scheduling problems with resource consuming jobs. Annals of Operations Research, 235(1):319-336, 2015. Google Scholar
  11. Péter Györgyi and Tamás Kis. Reductions between scheduling problems with non-renewable resources and knapsack problems. Theoretical Computer Science, 565:63-76, 2015. Google Scholar
  12. Tamás Kis. Approximability of total weighted completion time with resource consuming jobs. Operations Research Letters, 43(6):595-598, 2015. Google Scholar
  13. Alexander V Kononov and Bertrand MT Lin. Minimizing the total weighted completion time in the relocation problem. Journal of Scheduling, 13(2):123-129, 2010. Google Scholar
  14. Mikhail A Kubzin and Vitaly A Strusevich. Planning machine maintenance in two-machine shop scheduling. Operations Research, 54(4):789-800, 2006. Google Scholar
  15. Chung-Yee Lee. Machine scheduling with an availability constraint. Journal of global optimization, 9(3-4):395-416, 1996. Google Scholar
  16. Chinyao Low, Min Ji, Chou-Jung Hsu, and Chwen-Tzeng Su. Minimizing the makespan in a single machine scheduling problems with flexible and periodic maintenance. Applied Mathematical Modelling, 34(2):334-342, 2010. Google Scholar
  17. Ehab Morsy and Erwin Pesch. Approximation algorithms for inventory constrained scheduling on a single machine. Journal of Scheduling, 18(6):645-653, 2015. Google Scholar
  18. Kabir Rustogi and Vitaly A Strusevich. Simple matching vs linear assignment in scheduling models with positional effects: A critical review. European Journal of Operational Research, 222(3):393-407, 2012. Google Scholar
  19. Wayne E Smith. Various optimizers for single-stage production. Naval Research Logistics Quarterly, 3(1-2):59-66, 1956. Google Scholar
  20. Gerhard J Woeginger. When does a dynamic programming formulation guarantee the existence of a fully polynomial time approximation scheme (FPTAS)? INFORMS Journal on Computing, 12(1):57-74, 2000. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact