The job shop scheduling problem with convex costs
Reinhard Bürgy (reinhard.burgygerad.ca)
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.
Keywords: scheduling; job shop; non-regular objective; convex costs; tabu search
Category 1: Applications -- OR and Management Sciences
Category 2: Applications -- OR and Management Sciences (Scheduling )
Category 3: Combinatorial Optimization (Meta Heuristics )
Citation: Burgy, R. and Bulbul, K. (2018). The Job Shop Scheduling Problem with Convex Costs. European Journal of Operational Research, accepted for publication. Free access to the journal version at https://authors.elsevier.com/c/1WcLI1LnJ6XLT1 until 04/14/2018.
Entry Submitted: 06/27/2017
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|