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 |
| |
| Affiliation: | 1. Seton Hall University, 400 South Orange Avenue, NJ 07079, USA;2. Indian Institute of Management Calcutta, D.H. Road, Joka, Kolkata 700104, India;1. Case Western Reserve University Medical School and Center for Marital and Sexual Health of South Florida, West Palm Beach, FL, USA;2. Ixchelsis Ltd, Sandwich, UK;3. Therapy Research Services Ltd, Headcorn, UK;4. PPD France, Ivry-sur-Seine, France;1. Department of Chemistry, K.L.E. Society''s P. C. Jabin Science College (Autonomous), Vidyanagar, Hubballi, Karnataka 580031, India;2. Department of Chemistry, Mangalore University, Mangalagangotri, Karnataka 574199, India;1. Department of Mathematics and Statistics, University of Nebraska at Kearney, United States;2. Department of Mathematical and Statistical Sciences, University of Colorado Denver, United States;3. Department of Mathematics, University of Denver, United States;1. School of Mathematics and Statistics, Xidian University, Xi''an, Shaanxi, 710071, PR China;2. School of Mathematics and Statistics, Xiamen University of Technology, Xiamen, Fujian, 361024, PR China |
| |
| 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. |
| |
| Keywords: | Single machine scheduling Sequence-dependent setup Quadratic penalty Graph search Genetic algorithm |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
