Single machine scheduling with sum-of-logarithm-processing-times based deterioration

Na Yin, Liying Kang, Ping Ji, Ji Bo Wang

Research output: Journal article publicationJournal articleAcademic researchpeer-review

10 Citations (Scopus)

Abstract

In this study we consider the single machine scheduling problems with sum-of-logarithm-processing-times based deterioration, i.e., the actual job processing time is a function of the sum of the logarithm of the processing times of the jobs already processed. We show that even with the introduction of the sum-of-logarithm-processing-times based deterioration to job processing times, single machine makespan minimization problem remain polynomially solvable. But for the total completion time minimization problem, we show that the optimal schedule is not always V-shaped with respect to job normal processing times. Heuristic algorithms and computational results are presented for the total completion time minimization problem.
Original languageEnglish
Pages (from-to)303-309
Number of pages7
JournalInformation Sciences
Volume274
DOIs
Publication statusPublished - 1 Aug 2014

Keywords

  • Deteriorating job
  • Scheduling
  • Single machine

ASJC Scopus subject areas

  • Artificial Intelligence
  • Software
  • Control and Systems Engineering
  • Theoretical Computer Science
  • Computer Science Applications
  • Information Systems and Management

Cite this