Esta é a minha primeira experiência com um desafio de complexidade assintótica, embora eu esteja feliz com respostas inteiramente em código, desde que elas apresentem uma explicação de sua complexidade de tempo.

Eu tenho o seguinte problema.

Considere as tarefas T_1, ... T_n e procs M_1, ..., M_m. Cada tarefa leva um certo tempo para ser executada, dependendo dos procs.

Cada tarefa também custa uma certa quantia para executar, dependendo dos procs.

As tarefas precisam ser executadas em ordem estrita (elas não podem ser realizadas em paralelo) e leva tempo para alterar o processo. Uma tarefa não pode ser movida de um processo para outro após ter sido iniciada.

Finalmente, cada tarefa deve ser concluída em um determinado período de tempo.

a tarefa

O objetivo é fornecer um algoritmo (ou algum código) que, com cinco tabelas do formulário acima, minimize o custo total para concluir todas as tarefas e garanta que todas as tarefas sejam concluídas dentro dos prazos. Se isso não for possível, apenas informamos que isso não pode ser feito.

Ponto

Você deve fornecer a grande complexidade Oh da sua solução em termos das variáveis ​​n, me onde d é o último prazo. Não deve haver constantes desnecessárias em sua grande complexidade Oh. Portanto, O (n / 1000) deve ser escrito como O (n), por exemplo.

Sua pontuação é calculada simplesmente definindo n = 100, m = 100 ed = 1000 em sua complexidade declarada. Você quer a menor pontuação possível.

desempate

Em caso de empate, a primeira resposta vence.

notas adicionadas

log no tempo, a complexidade de uma resposta será tomada como base 2.

placar

• 10 ^ 202 de KSFT ( Python ) Primeiro enviado, então recebe a recompensa.
• 10 ^ 202 de Dominik Müller ( Scala )

Pontuação: 10 ^ 202

Eu meio que gostaria que tivéssemos suporte para LaTeX agora ...

Como ninguém mais respondeu, pensei em tentar, mesmo que não seja muito eficiente. Não tenho certeza de qual é o grande O disso.

Eu acho que funciona. Pelo menos, é o único caso de teste publicado.

Ele recebe entradas como na pergunta, exceto sem os rótulos de número de máquina ou tarefa e com ponto e vírgula em vez de quebras de linha.

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

Verificar todos - Scala

Pontuação estimada: 2m ^ n

Começo em cada máquina e repito todas as tarefas para criar todas as permutações através das tarefas com diferentes máquinas que cumprem os prazos. Ou seja, se tudo estiver dentro do prazo, eu obteria 9 caminhos possíveis com 2 máquinas e 3 tarefas. (m ^ n) Depois, segui o caminho com o menor custo.

A entrada está estruturada desta forma (-> explica as partes e, portanto, não deve ser inserida):

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

E aqui está o código:

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

Eu também tive uma idéia para começar por trás. Como você sempre pode escolher uma máquina com o menor custo, se o tempo for menor do que a diferença do prazo anterior para o novo. Mas isso não diminuiria o tempo de execução máximo se a tarefa com o melhor custo demorar mais do que o prazo final.

Atualizar

======

Aqui está outra configuração. Tempo:

M_1 2 2 2 7
M_2 1 8 5 10

custo:

M_1 4 4 4 4
M_2 1 1 1 1

mudar o tempo:

    M_1 M_2
M_1  0   2
M_2  6   0

custo do switch:

    M_1 M_2
M_1  0   2
M_2  2   0

prazos:

5 10 15 20

Como entrada no meu programa:

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

Este possui duas soluções: tempo: 18, custo: 15, caminho: Lista (M_1, M_1, M_1, M_2) tempo: 18, custo: 15, caminho: Lista (M_2, M_1, M_1, M_1)

O que levanta a questão de como isso deve ser tratado. Todos devem ser impressos ou apenas um? E se o tempo fosse diferente? Um com o menor custo e sem prazo perdido é suficiente ou também deve ser o de menor tempo?