Single-machine scheduling with decreasing time-dependent processing times to minimize total absolute differences in waiting times

Dan Wang, Yu Bin Wu, Ji Bo Wang, Ping Ji

Research output: Journal article publicationJournal articleAcademic researchpeer-review

3 Citations (Scopus)

Abstract

In this article we consider a single-machine scheduling problem with decreasing time-dependent job-processing times. Decreasing time-dependent job-processing times means that its processing time is a non-increasing function of its execution start time. The objective is to find a schedule that minimizes total absolute differences in waiting times. We show that the optimal schedule is V-shaped: jobs are arranged in the descending order of their normal processing times if they are placed before the job with the smallest normal processing time, but in the ascending order of their normal processing times if placed after it. We prove several other properties of an optimal schedule, and introduce two heuristic algorithms that are tested against a lower bound. We also provide computational results to evaluate the performance of the heuristic algorithms.
Original languageEnglish
Pages (from-to)444-453
Number of pages10
JournalJournal of the Chinese Institute of Industrial Engineers
Volume29
Issue number7
DOIs
Publication statusPublished - 1 Oct 2012

Keywords

  • scheduling
  • single-machine
  • time-dependent processing times
  • total absolute differences in waiting times

ASJC Scopus subject areas

  • Industrial and Manufacturing Engineering

Cite this