Este es mi primer experimento con un desafío de complejidad asintótica, aunque estoy contento con las respuestas enteramente en código siempre que vengan con una explicación de su complejidad temporal.

Tengo el siguiente problema.

Considere las tareas T_1, ... T_n y los procesos M_1, ..., M_m. Cada tarea tarda una cierta cantidad de tiempo en realizarse según los procesos.

Cada tarea también cuesta una cierta cantidad dependiendo de los procesos.

Las tareas deben realizarse en orden estricto (no pueden realizarse en paralelo) y lleva tiempo cambiar el proceso. Una tarea no se puede mover de un proceso a otro después de que se haya iniciado.

Finalmente, cada tarea debe completarse en un momento determinado.

la tarea

El objetivo es proporcionar un algoritmo (o algún código) que proporcione cinco tablas del formulario anterior, minimice el costo total para completar todas las tareas mientras se asegura de que todas las tareas se completen en sus plazos. Si esto no es posible, solo informamos que no se puede hacer.

Puntuación

Debe dar la gran complejidad Oh de su solución en términos de las variables n, myd, donde d es la última fecha límite. No debe haber constantes innecesarias en su gran complejidad Oh. Entonces O (n / 1000) debe escribirse como O (n), por ejemplo.

Su puntaje se calcula simplemente estableciendo n = 100, m = 100 yd = 1000 en su complejidad establecida. Quieres el puntaje más pequeño posible.

disyuntor

En caso de empate, la primera respuesta gana.

notas agregadas

log en el tiempo la complejidad de una respuesta se tomará en base 2.

tabla de puntuaciones

• 10 ^ 202 de KSFT ( Python ) Primero enviado, por lo que obtiene la recompensa.
• 10 ^ 202 de Dominik Müller ( Scala )

Puntuación: 10 ^ 202

Ojalá tuviéramos soporte para LaTeX ahora ...

Como nadie más ha respondido, pensé en intentarlo, aunque no es muy eficiente. Sin embargo, no estoy seguro de cuál es el gran O de eso.

Creo que funciona Al menos, lo hace para el único caso de prueba publicado.

Toma datos como en la pregunta, excepto sin las etiquetas de máquina o número de tarea, y con punto y coma en lugar de saltos de línea.

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 todo - Scala

Puntaje estimado: 2m ^ n

Comienzo desde cada máquina e itero sobre todas las tareas para crear todas las permutaciones a través de las tareas con diferentes máquinas que cumplen con los plazos. Es decir, si todo está a tiempo, obtendría 9 rutas posibles con 2 máquinas y 3 tareas. (m ^ n) Luego, tomo el camino con el costo más bajo.

La entrada está estructurada de esta manera (-> explica las partes y, por lo tanto, no debe ingresarse):

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

Y aquí está el 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)
    }
}

También tuve una idea para comenzar desde atrás. Dado que siempre puede elegir una máquina con el costo más bajo si el tiempo es menor, entonces la diferencia de la fecha límite anterior a la nueva. Pero eso no disminuiría el tiempo de ejecución máximo si la tarea con el mejor costo toma más tiempo que la última fecha límite.

Actualizar

======

Aquí hay otra configuración. hora:

M_1 2 2 2 7
M_2 1 8 5 10

costo:

M_1 4 4 4 4
M_2 1 1 1 1

tiempo de cambio:

    M_1 M_2
M_1  0   2
M_2  6   0

costo de cambio:

    M_1 M_2
M_1  0   2
M_2  2   0

plazos de entrega:

5 10 15 20

Como entrada en mi 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 tiene dos soluciones: tiempo: 18, costo: 15, ruta: Lista (M_1, M_1, M_1, M_2) tiempo: 18, costo: 15, ruta: Lista (M_2, M_1, M_1, M_1)

Lo que plantea la pregunta de cómo se debe manejar esto. ¿Se deben imprimir todos o solo uno? ¿Y si el tiempo fuera diferente? ¿Es uno con el costo más bajo y no tiene una fecha límite perdida suficiente o también debería ser el que tiene el tiempo más bajo?