Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6894870 | European Journal of Operational Research | 2018 | 37 Pages |
Abstract
The job shop scheduling literature has been dominated by a focus on regular objective functions - in particular the makespan - in its half a century long history. The last twenty years have encountered a spike of interest in other objectives, such as the total weighted tardiness, but research on non-regular objective functions has always been isolated and scattered. Motivated by this observation, we present a tabu search heuristic for a large class of job shop scheduling problems, where the objective is non-regular in general and minimizes a sum of separable convex cost functions attached to the operation start times and the differences between the start times of arbitrary pairs of operations. This problem definition generalizes a number of problems considered earlier in the literature. A particular notion of “critical paths” derived from the so-called timing problem is at the core of the proposed neighborhood definition exploited successfully in a tabu search algorithm. The computational results attest to the promise of our work.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Reinhard Bürgy, Kerem Bülbül,