Resource constrained parallel machine scheduling problems with machine eligibility restrictions: Mathematical and constraint programming based approaches

The research in this dissertation is motivated by a real-world scheduling problem in the injection molding department of an electrical appliance company and investigates three resource-constrained parallel machine scheduling problems with machine eligibility restrictions.The first problem assumes that processing times of all jobs are equal and aims to minimize total flow time. For this problem, two heuristic algorithms are proposed. The first one is a Lagrangian-based solution approach embedded into a subgradient optimization procedure. The second one is a problem specific heuristic. The performances of the proposed algorithms are evaluated by means of randomly generated test instances with different problem parameters.The second problem allows arbitrary processing times and aims to minimize makespan. For this problem, three optimization models, namely, integer programming (IP), constraint programming (CP), and combined IP/CP models, are developed. Four different CP search algorithms have been evaluated. The proposed models are then tested through medium size test problems and the efficiency of the proposed IP/CP combined model is demonstrated.The last problem considers the real case with 36 machines and real die-machine compatibility data. For this problem, IP/IP and IP/CP iterative approaches are proposed. Both approaches have a common loading phase where an IP model assigns the jobs to the machines. Subsequently, in the scheduling phase, two alternative models, namely, IP and CP are developed to construct the final schedule. The proposed approaches are evaluated by the test problems generated on real data, and the efficiency of IP/CP iterative approach is investigated.