import pandas as pd
import matplotlib.pyplot as plt
import matplotlib.colors as mcolors
from collections import defaultdict

# --- 1. Input Data ---
# The raw schedule data provided by the user (Job, Op, Machine, Start Time, Completion Time)
RAW_SCHEDULE_DATA = """Job J15 | Operations: 10 | Due Date: 829
  - Operation 1
    - Machine 7 | Processing Time: 96
    - Machine 5 | Processing Time: 22
    - Machine 9 | Processing Time: 44
    - Machine 10 | Processing Time: 73
    - Machine 1 | Processing Time: 76
    - Machine 11 | Processing Time: 48
    - Machine 13 | Processing Time: 38
    - Machine 3 | Processing Time: 60
    - Machine 14 | Processing Time: 25
    - Machine 6 | Processing Time: 86
  - Operation 2
    - Machine 4 | Processing Time: 24
    - Machine 5 | Processing Time: 32
    - Machine 13 | Processing Time: 50
    - Machine 6 | Processing Time: 33
    - Machine 7 | Processing Time: 12
    - Machine 2 | Processing Time: 37
    - Machine 1 | Processing Time: 63
    - Machine 15 | Processing Time: 64
    - Machine 9 | Processing Time: 80
    - Machine 8 | Processing Time: 53
    - Machine 12 | Processing Time: 28
    - Machine 3 | Processing Time: 70
    - Machine 10 | Processing Time: 75
    - Machine 11 | Processing Time: 43
    - Machine 14 | Processing Time: 28
  - Operation 3
    - Machine 6 | Processing Time: 76
    - Machine 7 | Processing Time: 80
    - Machine 14 | Processing Time: 14
    - Machine 15 | Processing Time: 14
    - Machine 12 | Processing Time: 19
    - Machine 8 | Processing Time: 33
    - Machine 13 | Processing Time: 56
    - Machine 1 | Processing Time: 79
    - Machine 2 | Processing Time: 77
    - Machine 9 | Processing Time: 11
  - Operation 4
    - Machine 5 | Processing Time: 51
    - Machine 4 | Processing Time: 84
    - Machine 12 | Processing Time: 32
    - Machine 13 | Processing Time: 94
    - Machine 9 | Processing Time: 29
    - Machine 8 | Processing Time: 54
    - Machine 14 | Processing Time: 77
    - Machine 11 | Processing Time: 81
    - Machine 10 | Processing Time: 18
    - Machine 7 | Processing Time: 65
    - Machine 15 | Processing Time: 18
  - Operation 5
    - Machine 12 | Processing Time: 96
    - Machine 3 | Processing Time: 73
    - Machine 11 | Processing Time: 57
    - Machine 14 | Processing Time: 39
    - Machine 7 | Processing Time: 20
    - Machine 5 | Processing Time: 46
    - Machine 10 | Processing Time: 70
    - Machine 13 | Processing Time: 21
    - Machine 6 | Processing Time: 77
    - Machine 15 | Processing Time: 64
    - Machine 1 | Processing Time: 92
    - Machine 4 | Processing Time: 99
  - Operation 6
    - Machine 11 | Processing Time: 40
    - Machine 2 | Processing Time: 74
    - Machine 6 | Processing Time: 91
    - Machine 14 | Processing Time: 78
    - Machine 1 | Processing Time: 59
    - Machine 10 | Processing Time: 20
    - Machine 4 | Processing Time: 60
    - Machine 15 | Processing Time: 99
    - Machine 12 | Processing Time: 93
    - Machine 5 | Processing Time: 17
    - Machine 3 | Processing Time: 76
    - Machine 7 | Processing Time: 82
    - Machine 13 | Processing Time: 72
    - Machine 9 | Processing Time: 29
  - Operation 7
    - Machine 3 | Processing Time: 92
    - Machine 2 | Processing Time: 57
    - Machine 4 | Processing Time: 38
    - Machine 10 | Processing Time: 23
    - Machine 11 | Processing Time: 43
    - Machine 12 | Processing Time: 86
    - Machine 7 | Processing Time: 57
    - Machine 8 | Processing Time: 62
    - Machine 13 | Processing Time: 92
    - Machine 6 | Processing Time: 27
    - Machine 15 | Processing Time: 35
    - Machine 1 | Processing Time: 35
    - Machine 9 | Processing Time: 56
    - Machine 14 | Processing Time: 10
  - Operation 8
    - Machine 11 | Processing Time: 84
    - Machine 10 | Processing Time: 54
    - Machine 1 | Processing Time: 60
    - Machine 14 | Processing Time: 83
    - Machine 3 | Processing Time: 20
    - Machine 7 | Processing Time: 34
    - Machine 12 | Processing Time: 64
    - Machine 15 | Processing Time: 33
    - Machine 5 | Processing Time: 89
    - Machine 6 | Processing Time: 24
    - Machine 4 | Processing Time: 72
    - Machine 8 | Processing Time: 96
    - Machine 9 | Processing Time: 90
    - Machine 13 | Processing Time: 81
  - Operation 9
    - Machine 13 | Processing Time: 86
    - Machine 14 | Processing Time: 66
    - Machine 4 | Processing Time: 14
    - Machine 6 | Processing Time: 47
    - Machine 11 | Processing Time: 25
    - Machine 9 | Processing Time: 21
    - Machine 2 | Processing Time: 41
    - Machine 10 | Processing Time: 39
    - Machine 1 | Processing Time: 63
    - Machine 15 | Processing Time: 12
    - Machine 8 | Processing Time: 68
    - Machine 7 | Processing Time: 59
    - Machine 3 | Processing Time: 52
    - Machine 12 | Processing Time: 69
    - Machine 5 | Processing Time: 26
  - Operation 10
    - Machine 14 | Processing Time: 49
    - Machine 13 | Processing Time: 97
    - Machine 2 | Processing Time: 31
    - Machine 5 | Processing Time: 73
    - Machine 8 | Processing Time: 99
    - Machine 10 | Processing Time: 24
    - Machine 6 | Processing Time: 95
    - Machine 4 | Processing Time: 95
    - Machine 12 | Processing Time: 66
    - Machine 11 | Processing Time: 34
    - Machine 15 | Processing Time: 56
    - Machine 1 | Processing Time: 54
    - Machine 3 | Processing Time: 46

Total operations to be scheduled: 150


Random problem instance created with hardcoded values.

Main Menu
1. Run Solver Menu
2. Exit
Enter the number of your choice: 1

Problem Data:
Number of jobs: 15
Number of machines: 15
Total operations to be scheduled: 150

Select an algorithm to run:
1. Gurobi LP + FBS + Local Search
2. Gurobi with Warmstart (run Gurobi LP + FBS + Local Search first)
3. Exit
Enter the number of your choice: 1

--- Running Gurobi LP + FBS + Local Search ---
Set parameter WLSAccessID
Set parameter WLSSecret
Set parameter LicenseID to value 2678405
Academic license 2678405 - for non-commercial use only - registered to mm___@students.aust.edu.lb
Set parameter MIPFocus to value 2

--- Gurobi LP Relaxation Results ---
Makespan Lower Bound: 192.00


--- Running FBS ---

ENTER BEAM WIDTH: 1
ENTER FILTER WIDTH: 1


--- FBS Results ---

F1 = 307.00 (M)      F2 = 3202.00 (f)      F3 = 0.00 (T)
          Runtime: 0.51 seconds



--- Final Schedule from FBS ---

Job     Op      Machine Start Time      Completion Time



J1      1       8               0.00            51.00
J2      1       6               0.00            33.00
J7      1       7               0.00            55.00
J8      1       9               0.00            51.00
J9      1       2               0.00            42.00
J11     1       5               0.00            18.00
J12     1       3               0.00            15.00
J13     1       4               0.00            22.00
J14     1       10              0.00            11.00
J14     2       1               11.00           33.00
J4      1       3               15.00           34.00
J12     2       5               23.00           39.00
J3      1       6               33.00           86.00
J13     2       1               33.00           63.00
J14     3       3               34.00           48.00
J12     3       4               39.00           63.00
J9      2       2               42.00           58.00
J6      1       3               48.00           102.00
J14     4       5               48.00           82.00
J1      2       8               51.00           62.00
J10     1       9               51.00           63.00
J9      3       10              58.00           100.00
J8      2       8               62.00           74.00
J2      2       1               63.00           102.00
J10     2       7               63.00           88.00
J13     3       4               63.00           121.00
J12     4       8               74.00           88.00
J3      2       2               86.00           100.00
J11     2       6               86.00           114.00
J5      1       7               93.00           150.00
J9      4       5               100.00          155.00
J10     3       2               100.00          136.00
J3      3       3               102.00          173.00
J6      2       9               102.00          115.00
J7      2       1               102.00          123.00
J2      3       8               105.00          172.00
J6      3       6               115.00          134.00
J4      2       10              116.00          144.00
J1      3       1               123.00          135.00
J7      3       9               123.00          133.00
J8      3       9               133.00          152.00
J7      4       1               135.00          152.00
J11     3       2               136.00          179.00
J10     4       4               140.00          175.00
J13     4       10              144.00          155.00
J5      2       6               150.00          172.00
J8      4       1               152.00          186.00
J9      5       10              155.00          239.00
J13     5       5               155.00          173.00
J2      4       8               172.00          197.00
J5      3       7               172.00          197.00
J3      4       3               173.00          202.00
J4      3       4               175.00          197.00
J14     5       9               177.00          227.00
J10     5       2               179.00          209.00
J7      5       5               180.00          197.00
J11     4       1               186.00          221.00
J1      4       7               197.00          210.00
J2      5       5               197.00          219.00
J5      4       4               197.00          214.00
J6      4       8               200.00          222.00
J12     5       3               205.00          239.00
J1      5       2               210.00          235.00
J4      4       7               210.00          225.00
J8      5       4               214.00          239.00
J3      5       6               216.00          227.00
J5      5       5               219.00          239.00
J6      5       1               222.00          239.00
J4      5       9               227.00          239.00
J11     5       6               227.00          239.00"""

def parse_schedule(raw_data):
    """Parses the raw text data into a pandas DataFrame."""
    data = []
    for line in raw_data.strip().split('\n'):
        if not line or line.startswith('-') or line.startswith('Job'):
            continue
        try:
            job_str, op_str, machine_str, start, completion = line.split()
            data.append({
                'Job': int(job_str[1:]),
                'Op': int(op_str),
                'Machine': int(machine_str),
                'Start': float(start),
                'Completion': float(completion),
                'Duration': float(completion) - float(start)
            })
        except ValueError as e:
            print(f"Skipping line due to parsing error: {line} ({e})")
            continue
    df = pd.DataFrame(data)
    # Ensure Job and Machine are integers for grouping
    df['Job'] = df['Job'].astype(int)
    df['Machine'] = df['Machine'].astype(int)
    return df

def validate_constraints(df):
    """Checks for Machine Capacity and Job Precedence constraints."""
    
    errors = []

    # --- 1. Machine Capacity (Resource Constraint) Check ---
    # No two operations on the same machine can overlap.
    machine_groups = df.sort_values(by='Start').groupby('Machine')
    
    for machine_id, group in machine_groups:
        # Group is already sorted by 'Start' time
        for i in range(1, len(group)):
            op_prev = group.iloc[i-1]
            op_curr = group.iloc[i]
            
            # Constraint check: Current start time must be >= Previous completion time
            if op_curr['Start'] < op_prev['Completion']:
                errors.append(
                    f"Machine Capacity Violation on Machine M{machine_id}: "
                    f"Job J{op_curr['Job']}-Op{op_curr['Op']} starts at {op_curr['Start']:.2f}, "
                    f"but previous operation J{op_prev['Job']}-Op{op_prev['Op']} finishes at {op_prev['Completion']:.2f}."
                )

    # --- 2. Job Precedence Check (Technological Constraint) ---
    # Operation n must start after operation n-1 on the same job finishes.
    job_groups = df.sort_values(by='Op').groupby('Job')
    
    for job_id, group in job_groups:
        # Group is already sorted by 'Op' ID
        for i in range(1, len(group)):
            op_prev = group.iloc[i-1]
            op_curr = group.iloc[i]
            
            # Constraint check: Current operation start time must be >= Previous operation completion time
            if op_curr['Op'] == op_prev['Op'] + 1: # Only check if ops are consecutive
                 if op_curr['Start'] < op_prev['Completion']:
                    errors.append(
                        f"Job Precedence Violation on Job J{job_id}: "
                        f"Operation Op{op_curr['Op']} starts at {op_curr['Start']:.2f}, "
                        f"but the preceding operation Op{op_prev['Op']} finishes at {op_prev['Completion']:.2f}."
                    )
            # If ops are not consecutive, it implies the original data might have missing operations, 
            # but we can't check that constraint without the original job structure.

    return errors

def analyze_utilization(df):
    """Calculates makespan, machine busy time, and utilization."""
    
    makespan = df['Completion'].max()
    print(f"\nOverall Makespan ($C_{{max}}$): {makespan:.2f}")
    
    machine_utilization = []
    
    machine_busy_times = df.groupby('Machine')['Duration'].sum()
    
    print("\n--- Machine Utilization Analysis ---")
    print(f"Total Schedule Time (Makespan): {makespan:.2f}")

    for machine_id, busy_time in machine_busy_times.sort_index().items():
        utilization = (busy_time / makespan) * 100
        machine_utilization.append({
            'Machine': machine_id,
            'Busy Time': busy_time,
            'Utilization (%)': utilization
        })
        print(f"M{machine_id}: Busy Time = {busy_time:<8.2f} | Utilization = {utilization:.2f}%")

    # Overall System Utilization (Average across all machines)
    num_machines = df['Machine'].nunique()
    total_busy_time = machine_busy_times.sum()
    total_machine_capacity = makespan * num_machines
    avg_utilization = (total_busy_time / total_machine_capacity) * 100
    
    print("-" * 40)
    print(f"Average Machine Utilization: {avg_utilization:.2f}%")
    
    return makespan, machine_utilization

def generate_gantt_chart(df):
    """Generates and displays a Gantt chart."""
    
    num_jobs = df['Job'].nunique()
    
    # Generate distinct colors for each job
    # Using 'tab10' for up to 10 jobs, or a larger map if needed
    colors = plt.cm.get_cmap('hsv', num_jobs) 
    job_colors = {job: colors(i) for i, job in enumerate(df['Job'].unique())}

    # Set up the plot
    fig, ax = plt.subplots(figsize=(18, 10))
    
    # Create the Gantt bars
    for index, row in df.iterrows():
        job_id = int(row['Job'])
        machine_id = row['Machine']
        start_time = row['Start']
        duration = row['Duration']
        op_id = int(row['Op'])
        
        # Plot the bar
        ax.barh(
            y=machine_id, 
            width=duration, 
            left=start_time, 
            height=0.8, 
            color=job_colors[job_id], 
            edgecolor='black'
        )
        
        # Add text label (Job-Op) in the center of the bar
        ax.text(
            x=start_time + duration/2, 
            y=machine_id, 
            s=f'J{job_id}-O{op_id}', 
            ha='center', 
            va='center', 
            fontsize=7,
            fontweight='heavy', # <--- NEW PARAMETER ADDED HERE 
            color='white' if job_colors[job_id][0] + job_colors[job_id][1] + job_colors[job_id][2] < 1.5 else 'black'
        )

    # --- Formatting ---
    
    # Axis labels
    # Set Y-axis labels and ticks (Machines)
    ax.set_yticks(df['Machine'].unique())
    ax.set_yticklabels([f'M{m}' for m in df['Machine'].unique()],fontsize=8.5)

    # --- AXIS LABEL FONT & BOLD ---
    # Define a font dictionary for bold axis labels
    axis_font = {'family': 'sans-serif', 'color': 'black', 'weight': 'heavy', 'size': 19}

    ax.set_xlabel('TIME', fontdict=axis_font)
    # Set Y-axis label to 'Machine' and apply the bold font style
    ax.set_ylabel('MACHINES', fontdict=axis_font, fontsize=15, fontweight='heavy')



    # --- TITLE POSITION ADJUSTMENT ---
    # 'pad' moves the title down from the top edge of the figure.
    # Increased 'pad' from 20 to 30 for a larger vertical offset.
    ax.set_title('Flexible Job Shop Schedule (Gantt Chart)', pad=10, fontsize=16, fontweight='bold')

    ax.grid(axis='x', linestyle='--', alpha=0.6)
    
    # X-axis limits
    max_time = df['Completion'].max()
    ax.set_xlim(0, max_time + 5)
    
    # Legend (using job colors)
    handles = [plt.Rectangle((0,0),1,1, color=job_colors[job]) for job in df['Job'].unique()]
    labels = [f'Job J{job}' for job in df['Job'].unique()]
    ax.legend(handles, labels, title='Jobs', loc='upper right', bbox_to_anchor=(1.078, 1))

    plt.tight_layout()
    plt.show()


if __name__ == "__main__":
    df_schedule = parse_schedule(RAW_SCHEDULE_DATA)
    
    # 1. Constraint Validation
    validation_errors = validate_constraints(df_schedule)
    
    print("==============================================")
    print("       SCHEDULE VALIDATION REPORT")
    print("==============================================")

    if validation_errors:
        print("\n*** ERROR: CONSTRAINTS VIOLATED ***")
        for error in validation_errors:
            print(f"- {error}")
        print("\nConclusion: The schedule is INCONSISTENT.")
    else:
        print("\n*** SUCCESS: NO CONSTRAINT VIOLATIONS FOUND ***")
        print("Conclusion: The schedule is CONSISTENT and FEASIBLE.")
        
    print("==============================================")

    # 2. Utilization Analysis
    makespan, _ = analyze_utilization(df_schedule)
    print("==============================================")

    # 3. Gantt Chart Generation
    print("\nGenerating Gantt Chart...")
    generate_gantt_chart(df_schedule)
