Scheduling start time dependent jobs to minimize the total weighted completion time

A. Bachman; Edwin Tai Chiu Cheng; A. Janiak; Chi To Ng

doi:10.1057/palgrave.jors.2601359

Scheduling start time dependent jobs to minimize the total weighted completion time

A. Bachman, Edwin Tai Chiu Cheng, A. Janiak, Chi To Ng

Research output: Journal article publication › Journal article › Academic research › peer-review

63 Citations (Scopus)

Abstract

This paper deals with a single machine scheduling problem with start time dependent job processing times. The job processing times are characterized by decreasing linear functions dependent on their start times. The problem is to find a schedule for which the total weighted completion time is minimized. It is proved that the problem is NP-hard. Some properties of special cases of the general problem are also given. Based on these results, two heuristic algorithms are constructed and their performance is compared.

Original language	English
Pages (from-to)	688-693
Number of pages	6
Journal	Journal of the Operational Research Society
Volume	53
Issue number	6
DOIs	https://doi.org/10.1057/palgrave.jors.2601359
Publication status	Published - 1 Jun 2002

Keywords

Computational analysis
Heuristics
Scheduling
Single machine
Start time dependent processing time

ASJC Scopus subject areas

Management of Technology and Innovation
Strategy and Management
Management Science and Operations Research

More information

10.1057/palgrave.jors.2601359

Cite this

@article{33a15389eca2449f9f8a600befdbf2e7,

title = "Scheduling start time dependent jobs to minimize the total weighted completion time",

abstract = "This paper deals with a single machine scheduling problem with start time dependent job processing times. The job processing times are characterized by decreasing linear functions dependent on their start times. The problem is to find a schedule for which the total weighted completion time is minimized. It is proved that the problem is NP-hard. Some properties of special cases of the general problem are also given. Based on these results, two heuristic algorithms are constructed and their performance is compared.",

keywords = "Computational analysis, Heuristics, Scheduling, Single machine, Start time dependent processing time",

author = "A. Bachman and Cheng, {Edwin Tai Chiu} and A. Janiak and Ng, {Chi To}",

year = "2002",

month = jun,

day = "1",

doi = "10.1057/palgrave.jors.2601359",

language = "English",

volume = "53",

pages = "688--693",

journal = "Journal of the Operational Research Society",

issn = "0160-5682",

publisher = "Taylor and Francis Ltd.",

number = "6",

}

TY - JOUR

T1 - Scheduling start time dependent jobs to minimize the total weighted completion time

AU - Bachman, A.

AU - Cheng, Edwin Tai Chiu

AU - Janiak, A.

AU - Ng, Chi To

PY - 2002/6/1

Y1 - 2002/6/1

N2 - This paper deals with a single machine scheduling problem with start time dependent job processing times. The job processing times are characterized by decreasing linear functions dependent on their start times. The problem is to find a schedule for which the total weighted completion time is minimized. It is proved that the problem is NP-hard. Some properties of special cases of the general problem are also given. Based on these results, two heuristic algorithms are constructed and their performance is compared.

AB - This paper deals with a single machine scheduling problem with start time dependent job processing times. The job processing times are characterized by decreasing linear functions dependent on their start times. The problem is to find a schedule for which the total weighted completion time is minimized. It is proved that the problem is NP-hard. Some properties of special cases of the general problem are also given. Based on these results, two heuristic algorithms are constructed and their performance is compared.

KW - Computational analysis

KW - Heuristics

KW - Scheduling

KW - Single machine

KW - Start time dependent processing time

UR - http://www.scopus.com/inward/record.url?scp=0036602498&partnerID=8YFLogxK

U2 - 10.1057/palgrave.jors.2601359

DO - 10.1057/palgrave.jors.2601359

M3 - Journal article

SN - 0160-5682

VL - 53

SP - 688

EP - 693

JO - Journal of the Operational Research Society

JF - Journal of the Operational Research Society

IS - 6

ER -

Scheduling start time dependent jobs to minimize the total weighted completion time

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this