Communications - Scientific Letters of the University of Zilina 2016, 18(11):55-58 | DOI: 10.26552/com.C.2016.1A.55-58

Uniform Workload Distribution Problems

Peter Czimmermann1, Stefan Pesko1, Jan Cerny2
1 Department of Mathematical Methods and Operations Research, Faculty of Management Science and Informatics, University of Zilina, Slovakia
2 Department of Exact Methods, Faculty of Management, University of Economics, Prague, Czech Republic

In this paper we review common studies from the years 1984-2015 of problems occurring in uniform scheduling of workload distributions. These problems were formulated first by Pesko in dealing with the practical problem of regular scheduling of service vehicles. Given the nonnegative, real matrix with daily records of vehicles as columns, we need to minimize some irregularity measure of row sums (workloads) by permuting matrix columns. The problem has various practical modifications, such as the weighted rows of matrix, workload uncertainty variance, graph approach of exchange of elements and generalized inverse formulations. Some of them are presented in the paper.

Keywords: regular scheduling; matrix permutation; irregularity measure; NP-hard problem

Published: March 31, 2016  Show citation

ACS AIP APA ASA Harvard Chicago Chicago Notes IEEE ISO690 MLA NLM Turabian Vancouver
Czimmermann, P., Pesko, S., & Cerny, J. (2016). Uniform Workload Distribution Problems. Communications - Scientific Letters of the University of Zilina, 18(1A), 55-58. doi: 10.26552/com.C.2016.1A.55-58
Share...
Download citation
  • BibTeX (.bib)
  • Bookends (.ris)
  • EasyBib (.ris)
  • EndNote (.enw)
  • EndNote 8 (.xml)
  • ISI WoS (.isi)
  • Medlars (.medlars)
  • Mendeley (.ris)
  • MODS (.xml)
  • Papers (.ris)
  • RefWorks (.txt)
  • RefManager (.ris)
  • RIS (.ris)
  • MS Word (.xml)
  • Zotero (.ris)
    • Open full article

    References

    1. COFFMAN, E. G., YANNAKAKIS, M.: Permuting Elements within Columns of a Matrix in order to Minimize Maximum Row Sum, Mathematics of Operations Research, 9(3):384390, 1984. Go to original source...
    2. CERNY, J., VASEK, K., PESKO, S., PALUCH, S., ENGELTHALLER, D.: Transport Scheduling and its Optimization (in Slovak), Research report III-8-9/03, Research Institute of Transport, 1986.
    3. CERNY, J., KLUVANEK, P.: Principles of Mathematical Theory of Transport (in Slovak), VEDA, Bratislava, 1991.
    4. TEGZE, M., VLACH, M.: On the Matrix Permutation Problem, Zeitschrift fur Operations-Research, 30(3), 1986. Go to original source...
    5. GAREY, M. R., JOHNSON, D. S.: Computers and Intractability, A Guide to the Theory of NP-completeness, Freeman: San Francisco, 1979.
    6. PESKO, S., HAJTMANEK, R.: Matrix Permutation Problem for Fair Workload Distribution, Mathematical Methods in Economics, 32nd international conference, Olomouc, 2014.
    7. PESKO, S., KAUKIC, M.: Stochastic Algorithm for Uniform Workload Distribution Problem, Proc. of 13th Intern. Conference Informatics, IEEE, Poprad, 2015.
    8. CZIMMERMANN, P., PESKO, S.: The Regular Permutation Scheduling on Graph, J. of Information, Control and Management Systems, vol. 1, No. 1, 2003.
    9. CZIMMERMANN, P.: A Note on using Graphs in Regular Scheduling Problems, Communications - Scientific Letters of the University of Zilina, vol. 5, No. 4, 2003. Go to original source...
    10. CZIMMERMANN, P.: The Most Regular Perfect Matchings in Graph, Studies of the University of Zilina, Mathematical Series, vol. 16, No. 1, 2003.
    11. EVEN, S., KARIV, O.: An Algorithm for Maximum Matching in General Graphs, Proc. of 16th Annual Symp. on Foundations of Computer Science IEEE, New York, 1975. Go to original source...
    12. PESKO, S.: The Matrix Permutation Problem in Interval Arithmetic, J. of Information, Control and Management Systems, vol. 4, No.1, 2006.
    13. PESKO, S., CERNY, J.: Uniform Splitting in Managerial Decision Making, Economics and Management, 9(4), 2006.
    14. PUCCETTI, G., RUSCHENDORF, L.: Computation of Sharp Bounds on the Distribution of a Function of Dependent Risk, J. of Computational and Applied Mathematics, 236(7), 2012. Go to original source...
    15. BOUDT, K., VANDUFFEL, S., VERBEKEN, K.: Block Rearranging Elements within Matrix Columns to Minimize the Variability of Row Sums, http://ssrn.com/abstract=2634669, 2015. Go to original source...
    16. DELL'OLMO, P., HANSEN, P., PALLOTTINO, S., STORCHI, G.: On Uniform k-partition Problems, Discrete Applied Mathematics, 150(1-3), 2005. Go to original source...
    17. PESKO, S.: Minimal Total Area Convex Set Partitioning Problem, Communications - Scientific Letters of the University of Zilina, vol. 11, No. 3, 2009. Go to original source...

    This is an open access article distributed under the terms of the Creative Commons Attribution 4.0 International License (CC BY 4.0), which permits use, distribution, and reproduction in any medium, provided the original publication is properly cited. No use, distribution or reproduction is permitted which does not comply with these terms.


    Return to the content