Decomposition-based job-shop scheduling with constrained clustering
summary
Proposes decomposition by a constrained clustering that partitions operations into time-window clusters of size total_ops/num_clusters while preserving job precedence by including predecessors when assigning items, then solves each cluster with Answer Set Programming under a fixed time budget and stitches schedules greedily. Features feeding clustering include Remaining Processing Time and Earliest Starting Time plus machine-centric Machine Load and dynamic values from FIFO/3D heuristics. Evaluation on hard benchmarks shows clustering plus ASP often beats plain heuristics and single-shot ASP within limited solve time.
AI-written summary · about
chapters (11)
- 0:00Start
- 4:45Job-shop Scheduling Problem (JSP)
- 7:12JSP graph with 4 jobs and 3 machines
- 8:42Clustering for JSP
- 10:53Cluster-wise JSP solving
- 15:35Machine Load (ML)
- 18:46Feature extraction summary
- 19:07Feature combinations
- 20:00Constrained clustering algorithm
- 24:17Conclusions
- 25:11Demirkos instances 50 X 15
related talks
29mMarketplace Logistic via Answer Set Programming
51mA.I. constraint optimization with OptaPlanner
20mBeyond Sequential Agents: Orchestrating Hierarchical Agents
57mOptimization AI in Java, made easy with OptaPlanner
31mLLMs can't optimize schedules, but AI can!
33mBatch Systems in Production with Kueue: Multi-Tenancy and Fungibility
46mIntroduction to constraint programming
33mTurning Fragmented GPU Clusters Into One Elastic Compute Pool