Please use this identifier to cite or link to this item:
For citation please use:
Main Title: Single Machine Scheduling with Weighted Nonlinear Cost
Author(s): Höhn, Wiebke
Jacobs, Tobias
Type: Research Paper
Abstract: We consider the problem of scheduling jobs on a single machine. Given a nonlinear cost function, we aim to compute a schedule minimizing the weighted total cost, where the cost of each job is defined as the cost function value at the job's completion time. Throughout the past decades, great effort has been made to develop fast optimal branch-and-bound algorithms for the case of quadratic costs. The practical efficiency of these methods heavily depends on the utilization of structural properties of optimal schedules such as order constraints, i.e., sufficient conditions for pairs of jobs to appear in a certain order. The first part of this paper substantially enhances and generalizes the known order constraints. We prove a stronger version of the global order conjecture by Mondal and Sen that has remained open since 2000, and we generalize the two main types of local order constraints to a large class of polynomial cost functions.
Subject(s): single machine scheduling
weighted quadratic completion times
nonlinear cost
Issue Date: 2011
Date Available: 17-Dec-2021
Language Code: en
DDC Class: 510 Mathematik
Series: Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
Series Number: 2011, 08
ISSN: 2197-8085
TU Affiliation(s): Fak. 2 Mathematik und Naturwissenschaften » Inst. Mathematik
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Format: Adobe PDF | Size: 175.75 kB
DownloadShow Preview

Item Export Bar

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.