Valiot - Job Shop Scheduling Optimization assesment

Problem

Optimize a job shop scheduler for 10 jobs across 3 machines with IoT sensor delays to minimize makespan (completion time).

Results Summary

Version	Makespan	Time	Speed Improvement
Original	random	30s to 40s	-
Fixed Seed	68	9.96s	3.3x
Greedy	78	0.000035s	280,000x
NEH	68	0.000146s	68,000x

Original Script Issues

• Brute force: Tests all 10! (3.6M) permutations one by one
• Random chaos: Recalculated delays on iot for each permutation making the optimization unpredictable as we had different results each run
• Performance: 30+ seconds execution time
• Poor design: Flat list for 2D data maked very hard and computational inefficient to understand which machine was free

Optimization Process

1. Fixed Random Seed (My Implementation)

Problem: Random delays recalculated for each of 3.6M permutations Solution: Generate delays once with fixed seed for deterministic optimization as well

random.seed(69)
sensor_delays = [[random.randint(0, 5) for _ in range(machines)] for _ in range(jobs)] #outside the iter loop

Impact: 3.3x faster, deterministic results

2. Greedy Algorithm (My Idea + Copilot)

Approach: Sort jobs by shortest calculated processing time first, i only used copilot autocomplete for this, not any llm magic yet Result: Ultra-fast but suboptimal (makespan 78 using this vs 68 that is the real best solution)

3. NEH Algorithm (AI-Assisted Research)

Process:

• Asked AI to research best scheduling algorithms since this is not my area of expertise but is cool to learn!
• Discovered NEH (Nawaz-Enscore-Ham) - industry standard since 1983
• Implemented with AI guidance, I love to tell IA to priotize simple solutions and kiss principles, because AI tends to overengineer a lot of stuff if not checked in line constantly

How NEH Works:

1. Sort jobs by total time (longest first)
2. Build schedule by inserting each job at optimal position
3. O(n²m) complexity vs O(n!) for brute force

Code Improvements:

• Extracted reusable calculate_makespan() function, with this we just track when one of the 3 machines will be free instead of the "Flat list for 2D data"
• Removed unnecessary flat list
• Clean simple and kiss code, we tried to remain as closest as possible to the original implementation

Results of each commit execution:

Commit: bea7639
Base state (random nonsense)

• Best order: (6, 8, 3, 9, 7, 4, 2, 5, 1, 0)
• Best order: (8, 4, 3, 6, 9, 1, 2, 0, 5, 7)
• Min makespan: 56
• Time taken: 33.19617176055908 seconds
• My comment: Best order was different each time and it took 30-40s to solve

Commit: ddde5fd
Before greedy (deterministic seed):

• Best order: (8, 1, 2, 3, 5, 4, 6, 7, 9, 0)
• Min makespan: 68
• Time taken: 9.961405754089355 seconds
• My comment: Min makespan is our baseline here, since this is the guaranteed best result since we tried all combinations for seed 69

Commit: d4eba98
After greedy approach:

• Best order: [1, 8, 9, 7, 0, 6, 3, 2, 4, 5]
• Min makespan: 78
• Time taken: 3.528594970703125e-05 seconds
• My comment: We reduced the execution time significantly, but we're not finding the most efficient makespan

Commit: 0e71e7f NEH algorithm:

• Best order: [8, 1, 6, 9, 2, 4, 7, 3, 5, 0]
• Min makespan: 68
• Time taken: 0.00014638900756835938 seconds
• My comment: We find the best makespan a bit slower, but this is what we really want