Please use this identifier to cite or link to this item: https://ir.iimcal.ac.in:8443/jspui/handle/123456789/403
Title: Application of Graph Search and Genetic Algorithms for the Single Machine Scheduling Problem with Sequence-Dependent Setup Times and Quadratic Penalty Function of Completion Times
Authors: Kodaganallur, Viswanathan
Sen, Anup K.
Mitra, Subrata
Keywords: Single machine scheduling
Sequence-dependent setup
Quadratic penalty
Graph search
Genetic algorithm
Issue Date: 1-Nov-2011
Publisher: INDIAN INSTITUTE OF MANAGEMENT CALCUTTA
Series/Report no.: WORKING PAPER SERIES;WPS No. 686/ November 2011
Abstract: In this paper, we consider the single machine scheduling problem with quadratic penalties and sequence-dependent (QPSD) setup times. QPSD is known to be NP-Hard. Only a few exact approaches, and to the best of our knowledge, no approximate approaches, have been reported in the literature so far. This paper discusses exact and approximate approaches for solving the problem, and presents empirical findings. We make use of a graph search algorithm, Memory- Based Depth-First Branch-and-Bound (MDFBB), and present an algorithm, QPSD_MDFBB that can optimally solve QPSD, and advances the state of the art for finding exact solutions. For finding approximate solutions to large problem instances, we make use of the idea of greedy stochastic search, and present a greedy stochastic algorithm, QPSD_GSA that provides moderately good solutions very rapidly even for large problems. The major contribution of the current paper is to apply QPSD_GSA to generate a subset of the starting solutions for a new genetic algorithm, QPSD_GEN, which is shown to provide near-optimal solutions very quickly. Owing to its polynomial running time, QPSD_GEN can be used for much larger instances than QPSD_MDFBB can handle. Experimental results have been provided to demonstrate the performances of these algorithms.
URI: https://ir.iimcal.ac.in:8443/jspui/handle/123456789/403
Appears in Collections:2011

Files in This Item:
File Description SizeFormat 
wps_686.pdf206.1 kBAdobe PDFThumbnail
View/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.