All Classes Namespaces Files Functions Variables Typedefs Enumerations Friends Macros Pages
scheduling_jobs_on_identical_parallel_machines.hpp
Go to the documentation of this file.
1 //=======================================================================
2 // Copyright (c) 2013 Piotr Smulewicz
3 //
4 // Distributed under the Boost Software License, Version 1.0. (See
5 // accompanying file LICENSE_1_0.txt or copy at
6 // http://www.boost.org/LICENSE_1_0.txt)
7 //=======================================================================
15 #ifndef PAAL_SCHEDULING_JOBS_ON_IDENTICAL_PARALLEL_MACHINES_HPP
16 #define PAAL_SCHEDULING_JOBS_ON_IDENTICAL_PARALLEL_MACHINES_HPP
17 
18 #include "paal/utils/functors.hpp"
20 #include "paal/utils/irange.hpp"
21 
22 #include <queue>
23 #include <vector>
24 #include <algorithm>
25 #include <utility>
26 
27 
28 namespace paal {
29 namespace greedy {
30 namespace detail {
31 class compare {
32  public:
33  compare(std::vector<int> &load) : m_load(load) {}
34  bool operator()(int lhs, int rhs) const {
35  return m_load[lhs] < m_load[rhs];
36  }
37 
38  private:
39  const std::vector<int> &m_load;
40 };
41 }
42 
57 template <class InputIterator, class OutputIterator, class GetTime>
59  InputIterator first,
60  InputIterator last,
61  OutputIterator result,
62  GetTime get_time) {
63  using JobReference =
64  typename std::iterator_traits<InputIterator>::reference;
66 
67  std::sort(first, last, utils::greater());
68  std::vector<int> load(n_machines);
69 
70  std::priority_queue<int, std::vector<int>, detail::compare> machines(load);
71 
72  for (auto machine_id : irange(n_machines)) {
73  machines.push(machine_id);
74  }
75  for (auto job_iter = first; job_iter < last; job_iter++) {
76  int least_loaded_machine = machines.top();
77  machines.pop();
78  load[least_loaded_machine] -= get_time(*job_iter);
79  machines.push(least_loaded_machine);
80  *result = std::make_pair(least_loaded_machine, job_iter);
81  ++result;
82  }
83 }
84 
85 }
86 }
87 
88 #endif // PAAL_SCHEDULING_JOBS_ON_IDENTICAL_PARALLEL_MACHINES_HPP
void scheduling_jobs_on_identical_parallel_machines(int n_machines, InputIterator first, InputIterator last, OutputIterator result, GetTime get_time)
detail
auto irange(T begin, T end)
irange
Definition: irange.hpp:22
This file contains set of simple useful functors or functor adapters.
greater functor
Definition: functors.hpp:478
typename std::decay< typename std::result_of< F >::type >::type pure_result_of_t
return pure type of function (decays const and reference)
double Time
[Scheduling Jobs Example]