The job shop scheduling problem with convex costs

Bürgy, Reinhard and Bülbül, Kerem (2018) The job shop scheduling problem with convex costs. European Journal of Operational Research, 268 (1). pp. 82-100. ISSN 0377-2217 (Print) 1872-6860 (Online)

This is the latest version of this item.

[thumbnail of This is a RoMEO green journal -- author can archive pre-print (ie pre-refereeing)] PDF (This is a RoMEO green journal -- author can archive pre-print (ie pre-refereeing))
JS-conv_Paper-GERADTemplate_2.pdf

Download (569kB)

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.
Item Type: Article
Uncontrolled Keywords: scheduling; job shop; non-regular objective; convex costs; tabu search
Subjects: T Technology > T Technology (General) > T055.4-60.8 Industrial engineering. Management engineering
T Technology > T Technology (General) > T055.4-60.8 Industrial engineering. Management engineering > T57.6-57.97 Operations research. Systems analysis
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Industrial Engineering
Faculty of Engineering and Natural Sciences
Depositing User: Kerem Bülbül
Date Deposited: 16 Aug 2018 11:49
Last Modified: 22 May 2023 15:25
URI: https://research.sabanciuniv.edu/id/eprint/34933

Available Versions of this Item

Actions (login required)

View Item
View Item