Single machine group scheduling with two ordered criteria

Edwin Tai Chiu Cheng, Mikhail Y. Kovalyov, Alexander V. Tuzikov

Research output: Journal article publicationJournal articleAcademic researchpeer-review

16 Citations (Scopus)

Abstract

The problem of scheduling jobs on a single machine is considered. It is assumed that the jobs are classified into several groups and the jobs of the same group have to be processed contiguously. A sequence independent set-up time is incurred between each two consecutively scheduled groups. A schedule is specified by a sequence for the groups and a sequence for the jobs in each group. The quality of a schedule is measured by two critera ordered by their relative importance. The objective is to minimize the maximum cost, the secondary criterion, subject to the schedule is optimal with respect to total weighted completion time, the primary criterion. A polynomial time algorithm is presented to solve this bicriterion group scheduling problem. It is shown that this algorithm can also be modified to solve the single machine group scheduling problem with several ordered maximum cost criteria and arbitrary precedence constraints.
Original languageEnglish
Pages (from-to)315-320
Number of pages6
JournalJournal of the Operational Research Society
Volume47
Issue number2
DOIs
Publication statusPublished - 1 Jan 1996

Keywords

  • Bicriterion scheduling
  • Single machine group scheduling

ASJC Scopus subject areas

  • Management Information Systems
  • Strategy and Management
  • Management Science and Operations Research
  • Marketing

Cite this