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.

Dit kan als volgt beschreven worden. We hebben een verzameling van \(n\) pakketten met vliegtijden \(p_1, p_2, \dots, p_n\), en \(m\) drones. We willen de pakketten verdelen over de drones. Als \(S_k\) de verzameling pakketten is die aan drone \(k\) worden toegewezen, dan is de totale werktijd van drone \(k\):

Het doel is om de totale tijd voor het afleveren van alle pakketten te minimaliseren: \(\min \max_{1 \leq k \leq m} T_k\). Met andere woorden: 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 dus geen oplossingen verder onderzoekt die zeker niet optimaal kunnen zijn. Implementeer eventueel ook één of meerdere heuristieken die heel snel een goede startoplossing vinden. Denk er ook over na of je het algoritme sneller kan maken door een specifieke volgorde te hanteren.

Met behulp van SimpleTest kan je jouw oplossing lokaal uittesten.