Affiliations: [a] Department of Computer Science, Campus de Viesques s/n, Gijón, University of Oviedo, Spain | [b] Department of Mathematics, Statistics and Computing, Los Castros s/n, Santander, University of Cantabria, Spain
Correspondence:
[*]
Corresponding author: Camino R. Vela, Department of Computer Science, Campus de Viesques s/n, Gijón, 33204, University of Oviedo. Spain. E-mail: [email protected].
Note: [1] This research has been supported by the Spanish Government under research grant TIN2016-79190-R.
Abstract: This paper tackles the job shop scheduling problem with fuzzy sets modelling uncertain durations and flexible due dates. The objective is to achieve high-service level by maximising due-date satisfaction, considering two different overall satisfaction measures as objective functions. We show how these functions model different attitudes in the framework of fuzzy multicriteria decision making and we define a measure of solution robustness based on an existing a-posteriori semantics of fuzzy schedules to further assess the quality of the obtained solutions. As solving method, we improve a memetic algorithm from the literature by incorporating a new heuristic mechanism to guide the search through plateaus of the fitness landscape. We assess the performance of the resulting algorithm with an extensive experimental study, including a parametric analysis, and a study of the algorithm’s components and synergy between them. We provide results on a set of existing and new benchmark instances for fuzzy job shop with flexible due dates that show the competitiveness of our method.
