A fastest algorithm optimization challenge

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 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.

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)
• "switching time from the row machine to the column machine" You mean the time cost to switch from M_1 to M_2? Also what's the difference between "switching cost" and "switching time". They typically mean the same thing in relation to describing scheduling algorithms. – Luminous Jan 21 '15 at 21:15
• @Luminous Think of time in seconds and cost in dollars. They are different things in this question. The tables show the time (respectively cost) of changing machine to perform the next task. This could be from M_1 to M_2 or from M_2 to M_1. – user9206 Jan 21 '15 at 21:27
• Ok, that clarifies that. – Luminous Jan 21 '15 at 21:31
• The short answer is that the complexity will be O(m ^ n). No algorithm will be "faster" than that. Pruning based on a maximum required time or cost doesn't change the complexity of the algorithm, nor does having both a dollar cost and a time cost, hence d is not an element of the complexity. – Bob Dalgleish Jan 22 '15 at 13:43
• @BobDalgleish That gives a score of 100 to the power of 100. I believe you can do a lot better. – user9206 Jan 22 '15 at 14:10

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)
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={}
for i in m:
t=-switchtime[i[-1]][i[0]]
c=-switchcost[i[-1]][i[0]]
e=0
t+=switchtime[i[e-1]][i[e]]+time[i[e]][j]
c+=switchcost[i[e-1]][i[e]]+cost[i[e]][j]
e+=1
d[(c,t)]=i
print min(d.keys()),d[min(d.keys())]

• Can you provide some explanation and say what you feel your score should be? Also, could you show what it gives for the example in the question? – user9206 Jan 22 '15 at 19:36
• As I stated in my answer, I have tried it and it does work on the example. I'm not sure what the big O is (which I meant to mention in my answer). – KSFT Jan 22 '15 at 19:53
• Basically, roughly how many operations will it take to complete. It looks like it takes ntasks*m time roughly (assume all the assignments in the loops take constant time) which make me suspicious about its correctness I have to admit. Can you say something about why you think it works? – user9206 Jan 22 '15 at 19:56
• Oh! I missed that. So m is in fact of size nmachines^ntasks . OK now I believe it works. I think your score is (100^100)*100 . – user9206 Jan 22 '15 at 20:02
• @Lembik It has the best score so far! – KSFT Jan 22 '15 at 20:03

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

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 parts = s.split(":")
(parts(0) -> parts(1).split(" ").map(_.toInt).toList)
}.toMap)

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)

(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) {
}
}

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)
}
}

val paths = machines.map(m => calculatePath(prev, task, m))
}

def calculatePath(prev: Path, task: Int, machine: String): Path = {

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


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?

• The question says that the goal is to "[minimize] the total cost". By the way, can you summarize how your algorithm works? I don't know Scala, and I can't figure out how this works. – KSFT Jan 28 '15 at 14:50
• Iterating over all of the paths takes O(m^n) time. Iterating over each machine for all of the tasks takes O(n*m^n) time. – KSFT Jan 28 '15 at 15:04
• Isn't O(n*m^n) iterating over each task for each of the paths? And Iterating over each machine for each tasks something like O(n*m). – Dominik Müller Jan 28 '15 at 15:58
• Ah, typo. I meant to write "Iterating over each machine for all of the paths takes O(n*m^n)". – KSFT Jan 28 '15 at 15:59
• Wait, no, it's O(m*m^n)=O(m^n+1). It's still the same score, though. – KSFT Jan 28 '15 at 16:00