Als pakjesbedrijf beschikken we over een aantal moderne drones die zelfstandig pakketjes kunnen afleveren. Elke drone kan maar één pakje tegelijk dragen en keert na afleveren meteen terug naar het depot. We kennen alle bestellingen voor vandaag, maar kunnen zelf nog kiezen in welke volgorde we de pakjes afleveren. Natuurlijk weten we ook voor ieder pakje precies hoe lang een drone erover zal doen het af te leveren en terug naar het depot te vliegen.
Nu vragen we ons af: op welke manier moeten we de pakketjes toewijzen aan de drones zodat de totale tijd die ze onderweg zijn zo klein mogelijk is? Anders gezegd: voor welke verdeling is de laatste drone het vroegst terug in het depot?

Dit probleem is niet makkelijk met de hand op te lossen, dus zullen we het automatiseren. Schrijf een branch-and-bound-algoritme dat gegeven de lijst met de vliegtijden per pakket, de vroegst mogelijke eindtijd teruggeeft.

Implementeer hiervoor de interface DroneScheduling¹ in een klasse MyDroneScheduling. Deze vereist een methode double minimalScheduleTime(List<Double> jobs, int numberOfDrones), die de optimale eindtijd teruggeeft voor een schedule met het meegegeven aantal drones. Je mag er vanuit gaan dat het aantal drones heel laag is (hoogstens 10).

Zorg ervoor dat je zoekfunctie op tijd snoeit en zo niet verderzoekt naar oplossingen die zeker niet optimaal kunnen zijn. Implementeer eventueel ook één of meerdere heuristieken die heel snel een goede startoplossing kunnen maken. Denk er ook eens over na of je het algoritme misschien sneller kan maken door een specifieke volgorde te hanteren.

Met behulp van SimpleTest² kan je jouw oplossing lokaal uittesten.