Minimizing the earliness-tardiness costs on a single machine

被引：20

作者：

Bauman, J

Józefowska, J

机构：

[1] Poznan Tech Univ, Inst Comp Sci, PL-60965 Poznan, Poland

[2] Bajsoft, PL-61207 Poznan, Poland

来源：

COMPUTERS & OPERATIONS RESEARCH | 2006年 / 33卷 / 11期

关键词：

scheduling; single machine; earliness-tardiness costs; just-in-time;

D O I：

10.1016/j.cor.2005.02.037

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

In this paper the one-machine scheduling problem with linear earliness and tardiness costs is considered. The cost functions are job dependent and asymmetric. The problem consists of two sub-problems. The first one is to find a sequence of jobs and the second one is to find the job completion times that are optimal for the given sequence. We consider the second sub-problem and propose an algorithm solving the problem in O(n log n) time. (c) 2005 Elsevier Ltd. All rights reserved.

引用

页码：3219 / 3230

页数：12

共 10 条

[1] DYNAMIC-PROGRAMMING STATE-SPACE RELAXATION FOR SINGLE-MACHINE SCHEDULING [J].