9
\$\begingroup\$

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)
\$\endgroup\$
13
  • \$\begingroup\$ "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. \$\endgroup\$
    – Luminous
    Jan 21, 2015 at 21:15
  • \$\begingroup\$ @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. \$\endgroup\$
    – user9206
    Jan 21, 2015 at 21:27
  • \$\begingroup\$ Ok, that clarifies that. \$\endgroup\$
    – Luminous
    Jan 21, 2015 at 21:31
  • \$\begingroup\$ 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. \$\endgroup\$ Jan 22, 2015 at 13:43
  • 1
    \$\begingroup\$ @BobDalgleish That gives a score of 100 to the power of 100. I believe you can do a lot better. \$\endgroup\$
    – user9206
    Jan 22, 2015 at 14:10

3 Answers 3

2
+50
\$\begingroup\$

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())]
\$\endgroup\$
8
  • \$\begingroup\$ 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? \$\endgroup\$
    – user9206
    Jan 22, 2015 at 19:36
  • \$\begingroup\$ 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). \$\endgroup\$
    – KSFT
    Jan 22, 2015 at 19:53
  • \$\begingroup\$ 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? \$\endgroup\$
    – user9206
    Jan 22, 2015 at 19:56
  • 1
    \$\begingroup\$ 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 . \$\endgroup\$
    – user9206
    Jan 22, 2015 at 20:02
  • 4
    \$\begingroup\$ @Lembik It has the best score so far! \$\endgroup\$
    – KSFT
    Jan 22, 2015 at 20:03
1
\$\begingroup\$

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?

\$\endgroup\$
5
  • \$\begingroup\$ 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. \$\endgroup\$
    – KSFT
    Jan 28, 2015 at 14:50
  • \$\begingroup\$ 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. \$\endgroup\$
    – KSFT
    Jan 28, 2015 at 15:04
  • \$\begingroup\$ 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). \$\endgroup\$ Jan 28, 2015 at 15:58
  • \$\begingroup\$ Ah, typo. I meant to write "Iterating over each machine for all of the paths takes O(n*m^n)". \$\endgroup\$
    – KSFT
    Jan 28, 2015 at 15:59
  • \$\begingroup\$ Wait, no, it's O(m*m^n)=O(m^n+1). It's still the same score, though. \$\endgroup\$
    – KSFT
    Jan 28, 2015 at 16:00
0
\$\begingroup\$

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.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ This is not an answer. You have to post the actual code. \$\endgroup\$
    – Optimizer
    Jan 20, 2015 at 23:02
  • \$\begingroup\$ 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! \$\endgroup\$
    – Doorknob
    Jan 20, 2015 at 23:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.