Single Machine Job Scheduling With Backward Forward Phase

Forward Phase Logic:

• Start with the sequence generated in the Backward Phase.
• Define lag k starting from N-1 down to 1.
• For each k, iterate j starting from k+1 (or appropriate range based on 0/1 indexing) to N.
• Exchange the job at position j with the job at position j-k.
• Calculate the total penalty of the new sequence.
• If the penalty decreases or stays the same (savings >= 0), accept the exchange. If the penalty decreases, restart the Forward Phase from k = N-1 (Step 1). If savings is zero, perform exchange and continue, unless the pair was previously checked.
• If the exchange increases penalty, reject it and increment j.
• Continue until k = 0.

Data Structure & Indexing:

• If the user requests 1-based indexing (e.g., jobs 1 to 40), use a dictionary for the jobs data structure where keys are integers 1 to N. This prevents IndexError common with list indexing.
• Job parameters include: processing_time, due_date, weight.

Output Requirements:

• Display the sequence and total penalty after the Backward Phase.
• Display the final best sequence and total penalty after the Forward Phase.
• Total penalty calculation: Sum of (max(0, CompletionTime - DueDate) * Weight) for all jobs.