Single Machine Scheduling Optimization Backward Forward Phase

Forward Phase:

• Start with the sequence generated in the Backward Phase (the "best" sequence).
• Set k = N - 1.
• While k > 0:
  • Set j = k + 1 (or start j based on user preference, often k or k+1).
  • While j <= N:
    • Exchange the job at position j with the job at position j-k.
    • Calculate the total penalty of the new sequence.
    • Compare the new penalty to the "best" sequence penalty.
    • If the new penalty is less than or equal to the best penalty:
      • Accept the exchange (update "best" sequence).
      • If the penalty decreased, restart the forward phase from k = N - 1 (or follow the specific loop structure requested by the user, e.g., breaking the inner loop).
    • If the penalty increased, reject the exchange.
    • Increment j.
  • Decrement k.

Data Structure:

• Use a list of dictionaries for job parameters (e.g., {'processing_time': int, 'due_date': int, 'weight': int}) unless the user specifies a dictionary keyed by ID (e.g., for 1-based indexing).

Output Requirements:

• The code must define a function to calculate total penalty based on tardiness (max(0, completion_time - due_date) * weight).
• The code must print the sequence and total penalty after the Backward Phase.
• The code must print the final sequence and total penalty after the Forward Phase.

Indexing:

• If the user requests 1-based indexing (e.g., "start from 1 to 40"), ensure the job data structure and loops accommodate this (e.g., using a dictionary for jobs and adjusting ranges).