Moore–Hodgson in Ada

Ada's strong typing and ranges fit naturally to scheduling — every quantity has a unit, and the compiler catches arithmetic mismatches.

1. 01
   Define types with semantic ranges. Ada's subtypes catch off-by-one and unit confusions at compile time — the kind of thing you really want when scheduling avionics tasks.

   with Ada.Containers.Vectors;
   procedure Job_Schedule is
      subtype Time     is Natural range 0 .. 1_000_000;
      subtype Penalty  is Natural;
   
      type Job is record
         Id          : Positive;
         Length      : Time;
         Deadline    : Time;
         Late_Cost   : Penalty;
      end record;
   
      package Job_Vectors is new Ada.Containers.Vectors
         (Index_Type => Positive, Element_Type => Job);
      use Job_Vectors;

2. 02
   Moore–Hodgson algorithm for minimizing the count of late jobs (a special case): sort by deadline, scan; whenever a job pushes you past its deadline, drop the longest scheduled-so-far. The algorithm is provably optimal for this objective.

   function Moore_Hodgson (Jobs : Vector) return Vector is
      Sorted : Vector := Jobs;
      Out_J  : Vector;
      T      : Time := 0;
   begin
      --  Sort by deadline (insertion sort, fine for small n)
      --  ... (sort code elided for space) ...
      for J of Sorted loop
         Out_J.Append (J);
         T := T + J.Length;
         if T > J.Deadline then
            declare
               Worst_Idx : Positive := 1;
            begin
               for K in Out_J.First_Index .. Out_J.Last_Index loop
                  if Out_J (K).Length > Out_J (Worst_Idx).Length then
                     Worst_Idx := K;
                  end if;
               end loop;
               T := T - Out_J (Worst_Idx).Length;
               Out_J.Delete (Worst_Idx);
            end;
         end if;
      end loop;
      return Out_J;
   end Moore_Hodgson;

3. 03
   Drive it. The result is the largest set of jobs that can all meet their deadlines on a single machine. Ada's compile-time guarantees are the reason it remains the language of choice for safety-critical scheduling — when an avionics scheduler reorders tasks, "off-by-one" is not an option.

      Jobs : Vector;
   begin
      Jobs.Append ((1, 5, 10, 100));
      Jobs.Append ((2, 4, 8,   50));
      Jobs.Append ((3, 6, 12,  20));
      declare
         Sched : constant Vector := Moore_Hodgson (Jobs);
      begin
         for J of Sched loop
            Ada.Text_IO.Put_Line ("scheduled " & Integer'Image (J.Id));
         end loop;
      end;
   end Job_Schedule;

4. 04
   For the general weighted case (the actually NP-hard Karp version), no greedy works; you fall back to branch-and-bound or branch-and-price. But the Moore–Hodgson kernel is the building block of every industrial scheduler, including those used by Boeing and Airbus.

   --  Weighted variant: branch on each job either scheduled-on-time
   --  or accepted-as-late, prune by lower-bound (sum of penalties for
   --  jobs that *must* be late given the chosen prefix).