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

17 Citations (Scopus)


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
Issue number2
Publication statusPublished - 1 Jan 1996


  • Bicriterion scheduling
  • Single machine group scheduling

ASJC Scopus subject areas

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


Dive into the research topics of 'Single machine group scheduling with two ordered criteria'. Together they form a unique fingerprint.

Cite this