Single machine scheduling with a restricted rate-modifying activity

Yong He, Min Ji, Edwin Tai Chiu Cheng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

30 Citations (Scopus)


In this paper we consider the problem of scheduling a set of jobs on a single machine on which a rate-modifying activity may be performed. The rate-modifying activity is an activity that changes the production rate of the machine. So the processing time of a job is a variable, which depends on whether it is scheduled before or after the rate-modifying activity. We assume that the rate-modifying activity can take place only at certain predetermined time points, which is a constrained case of a similar problem discussed in the literature. The decisions under consideration are whether and when to schedule the rate-modifying activity, and how to sequence the jobs in order to minimize some objectives. We study the problems of minimizing makespan and total completion time. We first analyze the computational complexity of both problems for most of the possible versions. The analysis shows that the problems are NP-hard even for some special cases. Furthermore, for the NP-hard cases of the makespan problem, we present a pseudo-polynomial time optimal algorithm and a fully polynomial time approximation scheme. For the total completion time problem, we provide a pseudo-polynomial time optimal algorithm for the case with agreeable modifying rates.
Original languageEnglish
Pages (from-to)361-369
Number of pages9
JournalNaval Research Logistics
Issue number4
Publication statusPublished - 1 Jun 2005


  • Approximation algorithms
  • Computational complexity
  • Rate-modifying activity
  • Scheduling

ASJC Scopus subject areas

  • Management Science and Operations Research

Cite this