Sequence-dependent scheduling with order deliveries

Miao-Tsong Lin*, P. Y. Yin, Y. S. Liu

*Corresponding author for this work

Research output: Contribution to journalArticle

Abstract

This paper studies a sequence-dependent scheduling problem incorporating order delivery, motivated by satellite imaging scheduling. A set of jobs is to be processed on a single machine and each job belongs to a specific group. The completion time of a group is the moment when all jobs belonging to this group are completed. The problem is to determine a processing sequence of the jobs such that the sum of weighted completion times over all groups is minimized. We present a binary integer program to formulate the studied problem and then develop an O(n 2 2 n ) dynamic programming algorithm for determining optimal solutions. To produce approximate solutions within an acceptable time, we design a tabu search algorithm, an iterated local search algorithm and a genetic algorithm. Computational experiments are conducted to study the performance of the integer program and the solution algorithms. Numerical statistics suggest that the binary integer program can reach optimal solutions faster than the integer program existing in the literature, and the iterated local search algorithm outperforms other approaches when the number of jobs increases.

Original languageEnglish
Pages (from-to)58-71
Number of pages14
JournalApplied Mathematics and Computation
Volume222
DOIs
StatePublished - 19 Aug 2013

Keywords

  • Meta-heuristics
  • Order delivery
  • Satellite imaging scheduling
  • Sequence-dependent setup
  • Total weighted completion time

Fingerprint Dive into the research topics of 'Sequence-dependent scheduling with order deliveries'. Together they form a unique fingerprint.

  • Cite this