bij job sequencing problem is het doel om de sequentie van banen te vinden, die binnen hun termijnen is voltooid en maximale winst te geven.
indien een reeks n banen wordt gegeven die verband houden met deadlines en winst wordt verdiend en een baan binnen de deadline is voltooid. Deze banen moeten zo worden geordend dat er een maximale winst is.
laten we een voorbeeld nemen. Zoals weergegeven in figuur 1.1 wordt een reeks banen gegeven waarbij elke baan een deadline en bijbehorende winst heeft als de baan vóór de deadline is voltooid. Het is ook gegeven dat elke baan duurt een eenheid van tijd, dus de minimum mogelijke deadline voor elke baan is 1. Hoe de totale winst te maximaliseren als slechts één taak tegelijk kan worden gepland.
een eenvoudige oplossing is om alle subsets van een bepaalde set taken te genereren en de individuele subset te controleren op de haalbaarheid van taken in die subset. Blijf op de hoogte van maximale winst tussen alle haalbare deelverzamelingen. De tijdscomplexiteit van deze oplossing is exponentieel.We kunnen dit probleem ook oplossen met behulp van hebzuchtige methode die meer optimaal is dan eenvoudige oplossing.Dus laten we dit probleem oplossen via hebzuchtige methode.
om de taak sequencing probleem via hebzuchtige methode op te lossen volg deze stappen:
- Sorteer alle banen in afnemende volgorde van winst.
- Initialiseer de resultaatreeks als eerste taak in gesorteerde taken.
- Volg voor de resterende n-1-banen.
- als de huidige taak in de huidige resultaatreeks past zonder de deadline te missen, voegt u de huidige taak toe aan het resultaat. Anders negeer je de huidige taak.
zoals u kunt zien in figuur 1.1 zijn de banen al in dalende volgorde van winst.Hier heeft job 1 de hoogste winst en de deadline is 3 dus zet die job tussen 2-3 zoals weergegeven in figuur 1.2.Job 2 heeft op een na hoogste winst en de deadline is 4 dus zet die baan tussen 3-4 en doe hetzelfde voor alle jobs.So de laatste reeks is J4-J3-J1-J2 en de totale winst is 110.
u kunt de code voor dit algoritme gebruiken op https://www.geeksforgeeks.org/job-sequencing-problem.
tijdscomplexiteit van deze oplossing is O (n2). het kan worden geoptimaliseerd door disjuncte gegevensstructuur.
hoop dat je het artikel leuk vindt.Dank u:)
