An Efficient Algorithm for a Bicriteria Single-Machine Scheduling Problem

Katoh, N. (1987). An Efficient Algorithm for a Bicriteria Single-Machine Scheduling Problem. IIASA Working Paper. IIASA, Laxenburg, Austria: WP-87-100

[thumbnail of WP-87-100.pdf]
Preview
Text
WP-87-100.pdf

Download (426kB) | Preview

Abstract

This paper considers a single-machine scheduling problem in which the maximum tardiness and the total flowtime are two objectives to be minimized. Instead of enumerating all efficient schedules, the author considers the problem of minimizing the maximum of the weighted values of these two objective functions, which arises in interactive multicriteria decision making. The author proposes a strongly polynomial algorithm for this problem which runs in O(n^2 log n) time.

Item Type: Monograph (IIASA Working Paper)
Research Programs: System and Decision Sciences - Core (SDS)
Depositing User: IIASA Import
Date Deposited: 15 Jan 2016 01:57
Last Modified: 27 Aug 2021 17:12
URI: https://pure.iiasa.ac.at/2952

Actions (login required)

View Item View Item