Graph coloring approaches for a production planning problem with makespan and setup penalties in a product-wheel context

Article Article scientifique Article Graph coloring approaches for a production planning problem with makespan and setup penalties in a product-wheel context eng 2024-10 author Cailloux Jocelin 948262 Recherche et enseignement GSEM (RESEM) author Zufferey Nicolas 0000-0002-4361-5510 664736 Recherche et enseignement GSEM (RESEM) author Gallay Olivier 200-222 10.1016/j.dam.2024.04.015 0166-218X https://linkinghub.elsevier.com/retrieve/pii/S0166218X2400163X <p>In this paper, we introduce a clustering and scheduling problem on a production line modeled as a single machine. A set of jobs (some of them being urgent) must be partitioned into clusters, and a robust (with respect to a min–max criterion) cyclic sequencing of the clusters must be determined (i.e., the product-wheel paradigm is employed). Each cluster has to satisfy two constraints: the setup constraint (i.e., only jobs with small setup times between them are allowed in the cluster) and the capacity constraint (i.e., the setup and processing times in the cluster cannot exceed a given shift duration). Three objective functions are minimized in a lexicographic fashion: (1) the number of urgent clusters (i.e., containing at least one urgent job); (2) the total number of clusters; (3) a worst-case scenario with respect to the setup among clusters. In other words, makespan and setup penalties are considered. Graph-coloring models and methods are designed for (1) and (2), whereas traveling-salesman approaches are introduced for (3). The considered problem was proposed by a micro-machining company located in Switzerland, named DIXI polytool. In order to cover their industrial needs, the company imposed very strict computing-time limitations (a few minutes only), and was able to provide realistic instances with different characteristics. Three methods are compared in our experiments: an integer linear model (with CPLEX), a constructive heuristic that represents a current-practice rule, and a metaheuristic relying on various tabu-search procedures. Results show the efficiency (with respect to quality and speed) of our metaheuristic, and managerial insights are provided.</p> Combinatorial optimization Metaheuristics Graph coloring for production planning Makespan and setup penalties Traveling salesman problem Scheduling Dewey 330/650 9 Faculté d'économie et de management S false Discrete applied mathematics 355 c8478bc8-e555-41bd-9820-4a40a45241a4 Article (Published version) Public 2024-Cailloux-Zufferey-Gallay-DAM.pdf 469341 application/pdf df1a1cb2795ee52000ed55a4d76698a57990261d5da96723cf739d1c87c3c0bc openAccess Faculté d'économie et de management

Title	Published in	Access level	OA Policy	Year	Views	Downloads

Graph coloring approaches for a production planning problem with makespan and setup penalties in a product-wheel context	Discrete applied mathematics			2024	66	385

Archive ouverte UNIGE

Cailloux, Jocelin