Resource Optimal Control in Some Single-Machine Scheduling Problems

Research output: Journal article publicationJournal articleAcademic researchpeer-review

62 Citations (Scopus)

Abstract

We consider a problem to schedule a set of jobs on a single machine under the constraint that the maximum job completion time does not exceed a given limit. Before a job is released for processing, it must undergo some preprocessing treatment which consumes resources. It is assumed that the release time of a job is a positive strictly decreasing continuous function of the amount of resources consumed. The objective is to minimize the total resource consumption. We show that ordering jobs in nonincreasing processing times yields an optimal solution. We then consider a bicriterion approach to the problem in which the maximum job completion time and the resource consumption are simultaneously minimized and present a polynomial time solution algorithm. Finally, we consider a related problem in which the job release times are given but the processing times are functions of the amount of resource consumed. We show that ordering jobs in nondecreasing release times gives an optimal solution and that the problem to minimize both the maximum compLetion time and resource consumption is polynomially solvable.
Original languageEnglish
Pages (from-to)1243-1246
Number of pages4
JournalIEEE Transactions on Automatic Control
Volume39
Issue number6
DOIs
Publication statusPublished - 1 Jan 1994

ASJC Scopus subject areas

  • Computer Science Applications
  • Control and Systems Engineering
  • Electrical and Electronic Engineering

Cite this