text:
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 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)

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

Ok, that clarifies that.

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.

@BobDalgleish That gives a score of 100 to the power of 100. I believe you can do a lot better.

Will the actual input have labels like M_1 and T_1?

@KSFT You can assume any sensible format for the input you like. I was assuming that each table would just be a list of tuples, each tuple representing a row of that table.

I'm not sure if I understand exactly how you're measuring time complexity. Do both answers currently have the same score? (If so, yay! The bounty would get me halfway to 1k rep!)

@KSFT  Assuming it is correct, O(2m^n) = O(m^n) which would give a score of 100^100. I am not yet sure if that 2 is really a constant or is secretly m. In this case it would be 100*100^100.

They both have complexity O(m^n), as BobDalgleish pointed out.

The 2 is in the exponent. They both take O(n*m^n) time.

@KSFT Looks like you both have identical scores.. so you win :)  I am bit sad no one tried dynamic programming which I think gives a much better score.

It looks like you never actually wrote in the question the secret information that times must be an integer between 0 and d, which made it impossible for anyone to use the m n^2 d solution.

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())]

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?

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

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?

@Lembik No, I know what the concept of big O is. I'm just not sure what the big O of this solution is. Also, itertools does a lot of the work, which is partly why I'm not sure what its big O is. Can you provide more test cases so that we can be more sure that it works?

Ah OK :) Doesn't it just have two nested loops? So it runs the inner loop m times and the inner loop takes roughly ntasks time.  I can make more test cases in theory but I am all tied up with work for a few days now. Sorry.

@Lembik No, it runs the inner loop len(m) times. My m isn't the same as your m.

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 .

@Lembik It has the best score so far!

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?

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.

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.

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

Ah, typo. I meant to write "Iterating over each machine for all of the paths takes O(n*m^n)".

Wait, no, it's O(m*m^n)=O(m^n+1). It's still the same score, though.

O(m2n) = 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 = m2. 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 m2 edges going to the next layer. So, we have a DAG with O(m2n) 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(m2n) time.

This is not an answer. You have to post the actual code.

Welcome to Programming Puzzles & Code Golf! Here on Stack Exchange, unlike other sites such as forums, we expect answers to fully address the question. On PPCG, that means that they should contain fully working code that attempts to solve the challenge. I'm deleting this, but feel free to edit in some working code and then flag for a moderator to undelete. Thanks!

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

sort: votes


text:
Billy Lost his Pen
tl;dr [True] Billy got a Stack Overflow pen from Tim Post. Billy was stupid enough to use the pen, knowing that he was not worthy. Billy's friend took the pen apart, so Billy put the pen in a drawer at his house, hoping he would eventually fix it. A year later, Billy can only find half of the pen's pieces, and not the main part that has the words "Stack Overflow" on it. [EndTrue] [Fake] Billy looked at his home security camera and saw that a burglar had come in his house while he was sleeping and taken his pen. Billy vows revenge! Why can't he just ask for another Stack Overflow pen? Because this is the last one in existence. [EndFake] Err, technically this whole thing is fake because my name isn't Billy.
Help Billy find the scumbag that stole his pen so he can ultimately deal mortal damage to him and get the other half of his pen back! You will use a World object that has the following methods:
objectsAtPosition(lon: Number, lat: Number)

This returns an array of strings. One string for every object at the specified longitude (lon) and latitude (lat). The possible strings are:
SUP - Super User Pen
SFP - Server Fault Pen
SOP - Stack Overflow Pen
BD - Bad Dog
GD - Good Dog
G - Giygas
destroyObjectAt(lon: Number, lat: Number, i)

This destroys the object at the specified longitude, latitude, and index. For example, if at a specified longitude (lon) and latitude (lat) there are two or more objects, destroy the nth object in the array depending on what the index (i) is. You will destroy every Giygas and every Bad Dog.
giveTreatToObjectAt(lon: Number, lat: Number, i)

This gives a treat to the object at the specified longitude (lon), latitude (lat), and index. For example, if at a specified longitude (lon) and latitude (lat) there are two or more objects, give a treat to the nth object in the array depending on what the index (i) is. You will give all good dogs a treat.
collectObjectAt(lon: Number, lat: Number, i)

This collects the object at the specified longitude (lon) and latitude (lat), and index. For example, if at a specified longitude (lon) and latitude (lat) there are two or more objects, collect the nth object in the array depending on what the index (i) is. You will collect Billy's Stack Overflow pen and nothing else or else you die. Keep in mind that there is only Billy's Stack Overflow pen left in existence.
You will index through every longitude and latitude value (look below) and treat every object found as they should be treated.
Longitude and latitude rage from 0-10. Iterate incrementing by 1. Treat lon and lat as integers if you'd like. Use whatever-based indexing the language you're coding this in uses. This is code-golf, so shortest bytes in code wins.
Every item is an array. Here's an example of what the Array would be like. It's a 2D Array, 10x10. Longitude brings you right and latitude brings you down. So longitude with 5 and latitude with 4 would select this:
['SO','SU'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example']
['SO','SU'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example']
['SO','SU'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example']
['SO','SU'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example']
['SO','SU'],['Example'],['Example'],['Example'],['Example'],['*Example*'],['Example'],['Example'],['Example'],['Example']
['SO','SU'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example']
['SO','SU'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example']
['SO','SU'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example']
['SO','SU'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example']
['SO','SU'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example'],['Example']

or
0→[item]1→[item]2→[item]3→[item]4→[item]5→[item]0↓[item][item][item][item]
  [item]  [item]  [item]  [item]  [item]  [item]1↓[item][item][item][item]
  [item]  [item]  [item]  [item]  [item]  [item]2↓[item][item][item][item]
  [item]  [item]  [item]  [item]  [item]  [item]3↓[item][item][item][item]
  [item]  [item]  [item]  [item]  [item][*item*]←4[item][item][item][item]
  [item]  [item]  [item]  [item]  [item]  [item]  [item][item][item][item]
  [item]  [item]  [item]  [item]  [item]  [item]  [item][item][item][item]
  [item]  [item]  [item]  [item]  [item]  [item]  [item][item][item][item]
  [item]  [item]  [item]  [item]  [item]  [item]  [item][item][item][item]
  [item]  [item]  [item]  [item]  [item]  [item]  [item][item][item][item]

In case you don't see it, it will select the item "Example" in the first one and the item "item" in the second one. I'm not sure how the human brain works, use your browser's search on page feature if you still don't see it.
PS:
If you don't know what a Giygas is, just know that you have to destroy it... or pray for your life by it (which ultimately destroys it anyway).

Geobits' SO mug gets used by family members all the time, but at least it isn't lost (yet).

@Geobits My SO mug was used by my 7-year-old cousin once who got it all dry in hot chocolate :/

Can we rename the "World" object or the methods that are provided by it, or do we use them named as stated?

After doing the problem, I think it could be more interesting if the API provided the world contents in a jagged 3d array or something like that. The fact that a method has to be called for each cell really forces you into some kind of iteration - in-memory data might allow for some Linq tricks or crazy pointer arithmetic.

@BMac So it's fair for everyone and easy to read (because we can't really run these) use the names provided. If the names are conflicting in any way, please tell me.

@BMac Yeah... this far into the challenge, I guess it won't really kill anyone if I add an example of its contents and change a rule just a bit... I mean, it'll just add one more thing you could do for a possible shortcut

I just noticed something o_O I was true to my word and fixed the post at exactly 4pm

Can I interprete method with two arguments as dyadic verb?

@FUZxxl What do you mean?

@TheWobbuffet Language only have functions (verbs) in infix notation. They can have one argument, like in f y or two, like in x f y. One-argument functions are called monadic functions, two-argument functions are called dyadic functions.

@FUZxxl Ah, I didn't know functions were called verbs

@TheWobbuffet Is this a yes or a no?

@FUZxxl Yes

C# - 272 bytes
I couldn't find too many tricks to do here outside of some for-loop shenanigans. I was hoping to use some Linq, but the index parts of the API made it difficult to make that work concisely.
class A{static void Main(string[] a){
for(int x=101,y,c;x-->0;)
for(y=101;y-->(c=0);)
foreach(string s in World.objectAtPosition(x,y)){
if(s=="SOP")World.collectObjectAt(x,y,c);
if(s=="BD"||s=="G")World.destroyObjectAt(x,y,c);
if(s=="GD")World.giveTreatToObjectAt(x,y,c);
c++;}}}

Here's my test code:
using System.Linq;
class A
{
    static void Main(string[] a)
    {
        for (int d = 0; d < 100; d++)
        {
        World.populate();

        for(int x=101,y,c;x-->0;)
        for(y=101;y-->(c=0);)
        foreach(string s in World.objectAtPosition(x,y))
        {
            if(s=="SOP")World.collectObjectAt(x,y,c);
            if(s=="BD"||s=="G")World.destroyObjectAt(x,y,c);
            if(s=="GD")World.giveTreatToObjectAt(x,y,c);
            c++;
        }

        World.verify();
        }
    }

    static class World
    {
        private static System.Collections.Generic.List<Item>[,] m_Map =
            new System.Collections.Generic.List<Item>[maxRange+1, maxRange+1];

        private static System.Random random = new System.Random();

        private const int maxRange = 100;
        private const int dogCount = 20;

        private class Item
        {
            public string id;
            public bool handled;

            public Item(string id)
            {
                this.id = id;
                this.handled = false;
            }
        }

        public static void populate()
        {
            for (int lat = 0; lat <= maxRange; lat++)
                for (int lon = 0; lon <= maxRange; lon++)
                    m_Map[lat, lon] = new System.Collections.Generic.List<Item>();
            addRandom("SUP");
            addRandom("SFP");
            addRandom("SOP");
            addRandom("G");
            for (int c = 0; c < dogCount; c++)
            {
                addRandom("BD");
                addRandom("GD");
            }
        }

        public static void verify()
        {
            for (int lat = 0; lat <= maxRange; lat++)
            {
                for (int lon = 0; lon <= maxRange; lon++)
                {
                    for (int index = 0; index < m_Map[lat, lon].Count; index++)
                    {
                        Item item = m_Map[lat, lon][index];
                        if (!item.handled && item.id != "SUP" && item.id != "SFP")
                        {
                            throw new System.Exception(string.Format("Didn't handle '{0}' at '{1},{2}:{3}'.",
                                item.id, lat, lon, index));
                        }
                    }
                }
            }
        }

        private static int randomCoord()
        {
            return random.Next(maxRange + 1);
        }

        private static void addRandom(string item)
        {
            int lat = randomCoord();
            int lon = randomCoord();
            m_Map[lat, lon].Add(new Item(item));
        }

        public static string[] objectAtPosition(int lat, int lon)
        {
            return m_Map[lat, lon].Select(item => item.id).ToArray();
        }

        public static void destroyObjectAt(int lat, int lon, int index)
        {
            Item item = m_Map[lat, lon][index];
            if (item.id == "G" || item.id == "BD")
                item.handled = true;
            else
                throw new System.InvalidOperationException(string.Format("Tried to destroy '{0}' at '{1},{2}-{3}'",
                    item.id, lat, lon, index));
        }

        public static void giveTreatToObjectAt(int lat, int lon, int index)
        {
            Item item = m_Map[lat, lon][index];
            if (item.id == "GD")
                item.handled = true;
            else
                throw new System.InvalidOperationException(string.Format("Tried to giveTreatTo '{0}' at '{1},{2}-{3}'",
                    item.id, lat, lon, index));
        }

        public static void collectObjectAt(int lat, int lon, int index)
        {
            Item item = m_Map[lat, lon][index];
            if (item.id == "SOP")
                item.handled = true;
            else
                throw new System.InvalidOperationException(string.Format("Tried to collect '{0}' at '{1},{2}-{3}'. You die.",
                    item.id, lat, lon, index));
        }
    }
}

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/