Λύσεις 2ης-3ης σειιράς Ασκήσεων
- Κυριακή, 1 Φεβρουαρίου 2015 - 12:00 π.μ. -
Έχουν αναρτηθεί στο φάκελο Εγγραφα/Ασκήσεις, οι λύσεις των σειρών 2 και 3.
Καλή επιτυχία στο διαγώνισμα
--
Σχετικά με το Πρόβλημα 1 της 2ης Σειράς (που δυσκόλεψε τους περισσότερους) σας παραθέτω ακολούθως ένα απλό γενικό στιγμιότυπο που εξαρτάται από την παράμετρο m>=2 της εισόδου: Δίνονται m εργασίες, με χρόνο επεξεργασίας m η καθεμία, και m+1 εργασίες, με χρόνο επεξεργασίας m-1 η καθεμία.
Παρατηρήστε ότι, στη 2η περίπτωση, όπου οι εργασίες είναι ταξινομημένες σε φθίνουσα διάταξη, το makespan της χρονοδρομολόγησης θα ισούται με 3m-2. Όμως, η βέλτιστη χρονοδρομολόγηση έχει makspan ίσο με 3m-3.
