A fastest algorithm optimization challenge

Question

This is my first experiment with an asymptotic complexity challenge although I am happy with answers entirely in code as long as they come with an explanation of their time complexity.

I have the following problem.

Consider tasks T_1, ... T_n and procs M_1, ... , M_m. Each task takes a certain amount of time to perform depending on the procs.

Each task also costs a certain amount to perform depending on the procs.

The tasks have to be done in strict order (they can't be done in parallel) and it takes time to change proc. A task can't be moved from one proc to another after it has been started.

Finally, each task must be completed by a certain time.

the task

The objective is to give an algorithm (or some code) that given five tables of the form above, minimizes the total cost to complete all the tasks while making sure all the tasks are completed by their deadlines. If this isn't possible we just report that it can't be done.

score

You should give the big Oh complexity of your solution in terms of the variables n, m and d, where d is the last deadline. There should be no unnecessary constants in your big Oh complexity. So O(n/1000) should be written as O(n), for example.

Your score is calculated simply by setting n = 100, m = 100 and d = 1000 into your stated complexity. You want the smallest score possible.

tie breaker

In the case of a tie, the first answer wins.

---

added notes

log in the time complexity of an answer will be taken base 2.

score board

• 10^202 from KSFT (Python) First submitted so gets the bounty.
• 10^202 from Dominik Müller (Scala)

Answer 1

Score: 10^202

I kinda wish we had LaTeX support now...

Since no one else has answered, I thought I'd try, even though is isn't very efficient. I'm not sure what the big O of it is, though.

I think it works. At least, it does for the only test case posted.

It takes input like in the question, except without the machine or task number labels, and with semicolons instead of line breaks.

import itertools
time = [[int(j) for j in i.split()] for i in raw_input().split(";")]
cost = [[int(j) for j in i.split()] for i in raw_input().split(";")]
nmachines=len(time)
ntasks=len(time[0])
switchtime = [[int(j) for j in i.split()] for i in raw_input().split(";")]
switchcost = [[int(j) for j in i.split()] for i in raw_input().split(";")]
deadline = [int(i) for i in raw_input().split()]
d={}
m=itertools.product(range(nmachines),repeat=ntasks)
for i in m:
    t=-switchtime[i[-1]][i[0]]
    c=-switchcost[i[-1]][i[0]]
    e=0
    meetsdeadline=True
    for j in range(ntasks):
        t+=switchtime[i[e-1]][i[e]]+time[i[e]][j]
        c+=switchcost[i[e-1]][i[e]]+cost[i[e]][j]
        e+=1
        if t>deadline[j]:
            meetsdeadline=False
    if meetsdeadline:
        d[(c,t)]=i
print min(d.keys()),d[min(d.keys())]

Answer 2

Check All - Scala

Estimated score: 2m^n

I start from each machine and iterate over all the tasks to create all permutations through the tasks with different machines that meet the deadlines. Meaning if everything is in time I would get 9 possible paths with 2 machines and 3 tasks. (m^n) Afterwards, I take the path with the lowest cost.

Input is structured like this (--> explains the parts and thus should not be entered):

M_1:5 3 5 4;M_2:4 2 7 5                 --> time
M_1:5 4 2 6;M_2:3 7 3 3                 --> cost
M_1:M_1}0 M_2}1;M_2:M_1}2 M_2}0         --> switch itme
M_1:M_1}0 M_2}2;M_2:M_1}1 M_2}0         --> switch cost
5 10 15 20                              --> deadlines

And here is the code:

package Scheduling

import scala.io.StdIn.readLine

case class Cost(task: Map[String, List[Int]])
case class Switch(machine: Map[String, Map[String, Int]])
case class Path(time: Int, cost: Int, machine: List[String])

object Main {

    def main(args: Array[String]) {
        val (machines, cost_time, cost_money, switch_time, switch_money, deadlines) = getInput

        val s = new Scheduler(machines, cost_time, cost_money, switch_time, switch_money, deadlines)
        s.schedule
    }

    def getInput(): (List[String], Cost, Cost, Switch, Switch, List[Int]) = {
        val cost_time = Cost(readLine("time to complete task").split(";").map{s => 
                val parts = s.split(":")
                (parts(0) -> parts(1).split(" ").map(_.toInt).toList)
            }.toMap)

        val cost_money = Cost(readLine("cost to complete task").split(";").map{s => 
                val parts = s.split(":")
                (parts(0) -> parts(1).split(" ").map(_.toInt).toList)
            }.toMap)

        val switch_time = Switch(readLine("time to switch").split(";").map{s => 
                val parts = s.split(":")
                (parts(0) -> parts(1).split(" ").map{t =>
                        val entries = t.split("}")
                        (entries(0) -> entries(1).toInt)
                    }.toMap)
            }.toMap)

        val switch_money = Switch(readLine("time to switch").split(";").map{s => 
                val parts = s.split(":")
                (parts(0) -> parts(1).split(" ").map{t =>
                        val entries = t.split("}")
                        (entries(0) -> entries(1).toInt)
                    }.toMap)
            }.toMap)

        val deadlines = readLine("deadlines").split(" ").map(_.toInt).toList

        val machines = cost_time.task.keys.toList

        (machines, cost_time, cost_money, switch_time, switch_money, deadlines)
    }
}

class Scheduler(machines: List[String], cost_time: Cost, cost_money: Cost, switch_time: Switch, switch_money: Switch, deadlines: List[Int]) {

    def schedule() {
        var paths = List[Path]()
        var alternatives = List[(Int, Path)]()

        for (i <- machines) {
            if (cost_time.task(i)(0) <= deadlines(0)) {
                paths = paths ::: List(Path(cost_time.task(i)(0), cost_money.task(i)(0), List(i)))
            }
        }

        val allPaths = deadlines.zipWithIndex.tail.foldLeft(paths)((paths, b) => paths.flatMap(x => calculatePath(x, b._1, b._2)))

        if (allPaths.isEmpty) {
            println("It is not possible")
        } else {
            println(allPaths.minBy(p=>p.cost).machine)
        }
    }

    def calculatePath(prev: Path, deadline: Int, task: Int): List[Path] = {
        val paths = machines.map(m => calculatePath(prev, task, m))
        paths.filter(p => p.time <= deadline)
    }

    def calculatePath(prev: Path, task: Int, machine: String): Path = {
        val time = prev.time + switch_time.machine(prev.machine.last)(machine) + cost_time.task(machine)(task)
        val cost = prev.cost + switch_money.machine(prev.machine.last)(machine) + cost_money.task(machine)(task)

        Path(time, cost, prev.machine :+ machine)
    }
}

I also had an idea to start from the back. Since you can always choose a machine with the lowest cost if the time is smaller then the difference from the previous deadline to the new one. But that wouldn't decrease the maximal runtime if the task with the better cost takes longer then the last deadline is timed.

Update

======

Here is another set up. time:

M_1 2 2 2 7
M_2 1 8 5 10

cost:

M_1 4 4 4 4
M_2 1 1 1 1

switch time:

    M_1 M_2
M_1  0   2
M_2  6   0

switch cost:

    M_1 M_2
M_1  0   2
M_2  2   0

deadlines:

5 10 15 20

As input into my program:

M_1:2 2 2 7;M_2:1 8 5 10
M_1:4 4 4 4;M_2:1 1 1 1
M_1:M_1}0 M_2}2;M_2:M_1}6 M_2}0
M_1:M_1}0 M_2}2;M_2:M_1}2 M_2}0
5 10 15 20

This one has two solutions: time: 18, cost: 15, path: List(M_1, M_1, M_1, M_2) time: 18, cost: 15, path: List(M_2, M_1, M_1, M_1)

Which raises the question how this should be handled. Should all be printed or just one? And what if the time would be different? Is one with the lowest cost and no missed deadline enough or should it also be the one with the lowest time?

Answer 3

O(m²n) = 1000000

I am sure this will be beaten, but I figure I will give this as a reference answer.

First, construct a Directed Acyclic Graph using the data. The graph will be built out of layers (kind of like a neural net, for those who are familiar with them). The first layer just has the start vertex, a placeholder. The next layer has m vertices, one for each machine. There is an edge from the start vertex to each of the m vertices, with path cost 0. These edges represent the initial choice of which machine to start on.

The next layer has another m vertices, again representing the m machines. This time, the number of edges from the previous layer to this layer is m*m = m². Each of these edges has a cost equal to running task 1 on the corresponding machine in the previous layer, plus switching to the corresponding machine in the next layer. It also has a second cost equal to the switching time (you can track these two costs are tuples).

Continue on in this way: we will have one layer for each task, plus the dummy "start" and "end" layers. Each of the first n-1 non-dummy layers has m² edges going to the next layer. So, we have a DAG with O(m²n) edges, and O(mn) vertices. Now we simply perform a topological sort on the DAG, but every time a total time cost exceeds the relevant deadline, we delete the edge that would violate the deadline, and keep going. DAG topological sorting can be done in O(|E| + |V|), so we get the answer (or lack thereof) in O(m²n) time.