Batching-based approaches for optimized packing of jobs in the spatial scheduling problem

Sudharshana Srinivasan*, J. Paul Brooks, Jill Hardin Wilson

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingChapter

Abstract

Spatial resources are often an important consideration in shipbuilding and large-scale manufacturing industries. Spatial scheduling problems (SSP) involve the non-overlapping arrangement of jobs within a limited physical workspace such that some scheduling objective is optimized. The jobs are typically heavy and occupy large areas, requiring that the same contiguous units of space be assigned throughout the duration of their processing time. This adds an additional level of complexity to the general scheduling problem. Since solving large instances using exact methods becomes computationally intractable, there is a need to develop alternate solution methodologies to provide near optimal solutions for these problems. Much of the literature focuses on minimizing the makespan of the schedule. We propose two heuristic methods for the minimum sum of completion times objective. Our approach is to group jobs into a batch and then apply a scheduling heuristic to the batches. We show that grouping jobs earlier in the schedule, although intuitive, can result in poor performance when jobs have sufficiently large differences in processing times. We provide bounds on the performance of the algorithms and also present computational results comparing the solutions to the optimal objective obtained from the integer programming formulation for SSP.With a smaller number of jobs, both algorithms produce comparable solutions. For instances with a larger number of jobs and a higher variability in spatial dimensions, we observe that the efficient area model outperforms the iterative model both in terms of solution quality and run time.

Original languageEnglish (US)
Title of host publicationSpringer Optimization and Its Applications
PublisherSpringer International Publishing
Pages243-263
Number of pages21
DOIs
StatePublished - Jan 1 2015

Publication series

NameSpringer Optimization and Its Applications
Volume105
ISSN (Print)1931-6828
ISSN (Electronic)1931-6836

Keywords

  • Approximation algorithms
  • Integer programs
  • Optimal packings
  • Spatial scheduling

ASJC Scopus subject areas

  • Economics, Econometrics and Finance(all)
  • Business, Management and Accounting(all)
  • Mathematics(all)
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Batching-based approaches for optimized packing of jobs in the spatial scheduling problem'. Together they form a unique fingerprint.

Cite this