One-machine job-scheduling with non-constant capacity - Minimizing weighted completion times

H.F. Amaddeo; H.F. Amaddeo; W.M. Nawijn; Aart van Harten

doi:10.1016/S0377-2217(96)00240-8

One-machine job-scheduling with non-constant capacity - Minimizing weighted completion times

H.F. Amaddeo, H.F. Amaddeo, W.M. Nawijn, Aart van Harten

Research output: Contribution to journal › Article › Academic › peer-review

2 Citations (Scopus)

155 Downloads (Pure)

Abstract

In this paper an n-job one-machine scheduling problem is considered, in which the machine capacity is time-dependent and jobs are characterized by their work content. The objective is to minimize the sum of weighted completion times. A necessary optimality condition is presented and we discuss some special cases where this condition is also sufficient. We prove that the problem is NP-complete. A branch-and-bound algorithm is developed for the case when the capacity function is a step function. Computational results for 1000 test problems are presented.

Original language	Undefined
Pages (from-to)	502-512
Number of pages	11
Journal	European journal of operational research
Volume	102
Issue number	3
DOIs	https://doi.org/10.1016/S0377-2217(96)00240-8
Publication status	Published - 1997

Keywords

IR-30131
METIS-140770

Access to Document

10.1016/S0377-2217(96)00240-8

Amaddeo97one

Cite this

@article{a4d84ae3f84848ee9a461832b25799d2,

title = "One-machine job-scheduling with non-constant capacity - Minimizing weighted completion times",

abstract = "In this paper an n-job one-machine scheduling problem is considered, in which the machine capacity is time-dependent and jobs are characterized by their work content. The objective is to minimize the sum of weighted completion times. A necessary optimality condition is presented and we discuss some special cases where this condition is also sufficient. We prove that the problem is NP-complete. A branch-and-bound algorithm is developed for the case when the capacity function is a step function. Computational results for 1000 test problems are presented.",

keywords = "IR-30131, METIS-140770",

author = "H.F. Amaddeo and H.F. Amaddeo and W.M. Nawijn and {van Harten}, Aart",

year = "1997",

doi = "10.1016/S0377-2217(96)00240-8",

language = "Undefined",

volume = "102",

pages = "502--512",

journal = "European journal of operational research",

issn = "0377-2217",

publisher = "Elsevier",

number = "3",

}

TY - JOUR

T1 - One-machine job-scheduling with non-constant capacity - Minimizing weighted completion times

AU - Amaddeo, H.F.

AU - Nawijn, W.M.

AU - van Harten, Aart

PY - 1997

Y1 - 1997

N2 - In this paper an n-job one-machine scheduling problem is considered, in which the machine capacity is time-dependent and jobs are characterized by their work content. The objective is to minimize the sum of weighted completion times. A necessary optimality condition is presented and we discuss some special cases where this condition is also sufficient. We prove that the problem is NP-complete. A branch-and-bound algorithm is developed for the case when the capacity function is a step function. Computational results for 1000 test problems are presented.

AB - In this paper an n-job one-machine scheduling problem is considered, in which the machine capacity is time-dependent and jobs are characterized by their work content. The objective is to minimize the sum of weighted completion times. A necessary optimality condition is presented and we discuss some special cases where this condition is also sufficient. We prove that the problem is NP-complete. A branch-and-bound algorithm is developed for the case when the capacity function is a step function. Computational results for 1000 test problems are presented.

KW - IR-30131

KW - METIS-140770

U2 - 10.1016/S0377-2217(96)00240-8

DO - 10.1016/S0377-2217(96)00240-8

M3 - Article

SN - 0377-2217

VL - 102

SP - 502

EP - 512

JO - European journal of operational research

JF - European journal of operational research

IS - 3

ER -