Optimal interval scheduling with nonidentical given machines

We consider an interval scheduling problem where n jobs are required to be carried out by m nonidentical machines in an offline-scheduling way. Each job has a starting time, a finishing time and a number of processing units. Every machine has different number of processing units to carry out jobs. A machine can process only one job at a time without interrupted on the condition that the number of its units must satisfy job’s requirement. Further more, all units in one machine consume energy if the machine is powered up. Within this setting, one is asked to find a proper schedule of machines so that the total number of working units is as less as possible. For this interval scheduling problem, we first discuss an exact method based on integer programming which can be solved by branch-and-bound algorithm. Then, we propose two approximated methods named GreedyBS and GreedyMR using greedy strategy. GreedyBS is proved to be a 2.1343-approximated algorithm. All proposed algorithms are tested on a large set of randomly generated instances. It turns out that GreedyBS requires less total units of machines under time constrain when comparing with GreedyMR and exact methods in most cases, while GreedyMR costs the minimum time. Several parameters of GreedyBS and GreedyMR were also evaluated to improve the performances of these two algorithms.