C'est ma première expérience avec un défi de complexité asymptotique bien que je sois satisfait des réponses entièrement en code tant qu'elles sont accompagnées d'une explication de leur complexité temporelle.

J'ai le problème suivant.

Considérez les tâches T_1, ... T_n et les procs M_1, ..., M_m. Chaque tâche prend un certain temps à effectuer en fonction des procs.

Chaque tâche coûte également un certain montant à effectuer en fonction des procs.

Les tâches doivent être effectuées dans un ordre strict (elles ne peuvent pas être effectuées en parallèle) et il faut du temps pour changer de proc. Une tâche ne peut pas être déplacée d'un processus à un autre après son démarrage.

Enfin, chaque tâche doit être terminée avant un certain temps.

la tâche

L'objectif est de donner un algorithme (ou un code) qui, compte tenu des cinq tableaux du formulaire ci-dessus, minimise le coût total pour terminer toutes les tâches tout en s'assurant que toutes les tâches sont terminées dans leurs délais. Si cela n'est pas possible, nous signalons simplement que cela ne peut pas être fait.

But

Vous devez donner la grande complexité Oh de votre solution en termes de variables n, m et d, où d est la dernière échéance. Il ne devrait pas y avoir de constantes inutiles dans votre grande complexité Oh. Ainsi O (n / 1000) doit être écrit comme O (n), par exemple.

Votre score est calculé simplement en définissant n = 100, m = 100 et d = 1000 dans votre complexité déclarée. Vous voulez le plus petit score possible.

tie break

En cas d'égalité, la première réponse l'emporte.

notes ajoutées

log dans le temps la complexité d'une réponse sera prise en base 2.

tableau des scores

• 10 ^ 202 de KSFT ( Python ) Le premier soumis ainsi obtient la prime.
• 10 ^ 202 de Dominik Müller ( Scala )

Résultat: 10 ^ 202

J'aimerais un peu que nous ayons le support de LaTeX maintenant ...

Puisque personne d'autre n'a répondu, j'ai pensé que j'essaierais, même si ce n'est pas très efficace. Je ne sais pas quel est le gros O, cependant.

Je pense que ça marche. Du moins, c'est le cas pour le seul cas de test publié.

Il prend une entrée comme dans la question, sauf sans les étiquettes de numéro de machine ou de tâche, et avec des points-virgules au lieu des sauts de ligne.

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

Tout vérifier - Scala

Score estimé: 2m ^ n

Je pars de chaque machine et itère sur toutes les tâches pour créer toutes les permutations à travers les tâches avec différentes machines qui respectent les délais. Ce qui signifie que si tout est à temps, j'obtiendrais 9 chemins possibles avec 2 machines et 3 tâches. (m ^ n) Ensuite, je prends le chemin le moins cher.

L'entrée est structurée comme ceci (-> explique les parties et ne doit donc pas être entrée):

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

Et voici le 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)
    }
}

J'ai également eu une idée de partir de l'arrière. Puisque vous pouvez toujours choisir une machine avec le coût le plus bas si le temps est plus petit que la différence entre la date limite précédente et la nouvelle. Mais cela ne diminuerait pas le temps d'exécution maximal si la tâche avec le meilleur coût prend plus de temps que la dernière échéance est chronométrée.

Mise à jour

======

Voici une autre configuration. temps:

M_1 2 2 2 7
M_2 1 8 5 10

Coût:

M_1 4 4 4 4
M_2 1 1 1 1

temps de commutation:

    M_1 M_2
M_1  0   2
M_2  6   0

coût de commutation:

    M_1 M_2
M_1  0   2
M_2  2   0

délais:

5 10 15 20

Comme entrée dans mon programme:

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

Celui-ci a deux solutions: temps: 18, coût: 15, chemin: liste (M_1, M_1, M_1, M_2) temps: 18, coût: 15, chemin: liste (M_2, M_1, M_1, M_1)

Ce qui soulève la question de savoir comment cela doit être géré. Tous devraient-ils être imprimés ou un seul? Et si le temps était différent? Est-ce celui qui a le coût le plus bas et aucune échéance manquée ou devrait-il également être celui qui a le temps le plus bas?