A nested location-routing heuristic using route length estimation

A nested heuristic approach that uses route length approximation is proposed to solve the location-routing problem. A new estimation formula for route length approximation is also developed. The heuristic is evaluated empirically against the sequential method and a recently developed nested method for location routing problems. This testing is carried out on a set of problems of 400 customers and around 15 to 25 depots with good results.

Heuristics for short route job shop scheduling problems

We consider two “minimum”NP-hard job shop scheduling problems to minimize the makespan. In one of the problems every job has to be processed on at most two out of three available machines. In the other problem there are two machines, and a job may visit one of the machines twice. For each problem, we define a class of heuristic schedules in which certain subsets of operations are kept as blocks on the corresponding machines. We show that for each problem the value of the makespan of the best schedule in that class cannot be less than 3/2 times the optimal value, and present algorithms that guarantee a worst-case ratio of 3/2.

A 3/2 algorithm for two-machine open shop with route-dependent processing times

This paper considers the problem of minimizing the schedule length of a two-machine shop in which not only can a job be assigned any of the two possible routes, but also the processing times depend on the chosen route. This problem is known to be NP-hard. We describe a simple approximation algorithm that guarantees a worst-case performance ratio of 2. We also present some modifications to this algorithm that improve its performance and guarantee a worst-case performance ratio of 3=2.

Heuristics for short route job shop scheduling problems

Abstract not available