Optimal and Suboptimal Scheduling of the Dual Resource Job Shop Problem with Multi-Skilled Workforce

Abstract

Efficient production scheduling is important for reducing costs, meeting delivery deadlines, and balancing workloads in manufacturing environments. This thesis investigates scheduling optimization for a multi-skilled workforce derived from the production environment at Thorlabs Sweden AB. The problem is modelled as a dualresource flexible job shop problem (DR-FJSP), where both machines and workers must be available simultaneously in order to execute some operations, and where workers hold varying qualifications across product types. Five solution approaches are developed and evaluated: a mixed integer linear programming (MILP) formulation implemented in Gurobi, a satisfiability modulo theories (SMT) formulation implemented in Z3, a constraint programming (CP) model using Google OR-Tools CP-SAT, a genetic algorithm (GA), and a greedy priority-rule heuristic. The models incorporate sequence-dependent setup and cleaning times, operation-type constraints, and worker qualification requirements. The approaches are benchmarked on 100 synthetic instances and evaluated on real production instances in terms of solution quality and computational efficiency. The benchmark results show that ORTools solved the greatest number (57/100) of instances to optimality with a time limit of one hour. The CP-SAT implementation scaled better than both Gurobi and Z3 on the evaluated benchmark set, though all three exact methods are inferior to the GA in terms of runtime scaling on larger instances. The GA, seeded with heuristic solutions consistently improves upon the heuristic baseline across key performance indicators including makespan, total completion time, tardiness, and lateness, while remaining tractable for production-scale instances.