A Dial-a-Ride evaluation for solving the job-shop with routing considerations

Abstract : The Job-Shop scheduling Problem with Transport (JSPT) is a combinatorial optimization problem that combines both scheduling and routing problems. It has received attention for decades, resulting in numerous publications focused on the makespan minimization. The JSPT is commonly modeled by a disjunctive graph that encompasses both machine-operations and transport-operations. The transport-operations define a sub-problem which is close to the DARP where pickup and delivery operations have to be scheduled. The vast majority of the evaluation functions used into disjunctive graphs of JSPT, minimizes the makespan and there is no routing criteria in the objective function. Commonly used evaluation functions lead to left-shifted solutions for both machine-operations and transport-operations. The present work investigates a new evaluation function for the JSPT which integrates routing problematic to compute non semi-active solutions but which minimize the makespan first and maximize the Quality of Service second thanks to a time-lag max based modeling and an iterative process. The Quality of Service proposed in this paper, is extended from the Quality of Service defined by (Cordeau and Laporte, 2003) for the DARP. The procedure performance is benchmarked with a CPLEX resolution and the numerical experiments proved that the proposed evaluation function is nearly optimal and provides new solutions with a high Quality of Service.
Complete list of metadatas

https://hal.laas.fr/hal-01822071
Contributor : Marie-Jose Huguet <>
Submitted on : Saturday, June 23, 2018 - 2:20:58 PM
Last modification on : Monday, January 20, 2020 - 12:14:06 PM

Identifiers

Citation

Matthieu Gondran, Marie-José Huguet, Philippe Lacomme, Alain Quilliot, Nikolay Tchernev. A Dial-a-Ride evaluation for solving the job-shop with routing considerations. Engineering Applications of Artificial Intelligence, Elsevier, 2018, 74, pp.70-89. ⟨10.1016/j.engappai.2018.05.010⟩. ⟨hal-01822071⟩

Share

Metrics

Record views

242