Improved algorithm for single machine scheduling with release dates

Kai Li; Huawei Ma; Shanlin Yang

Improved algorithm for single machine scheduling with release dates

Kai Li
, Huawei Ma
, Shanlin Yang

School of Management

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

2 Scopus citations

Abstract

This paper considered the single machine scheduling problem with unequal release dates so as to minimize total completion times. This problem was proved to be as an NP-hard problem. Traditional heuristics for the problem were analyzed, and then we presented an improved algorithm. A numerical example and its computational result were given. The performance of the algorithm was also analyzed by experiments and the experimental results show that the algorithm is more effective than the existing heuristics.

Original language	English
Pages (from-to)	929-932
Number of pages	4
Journal	Zhongguo Jixie Gongcheng/China Mechanical Engineering
Volume	19
Issue number	8
State	Published - 25 Apr 2008

Keywords

Heuristic algorithm
Release date
Single machine scheduling
Total completion times

Cite this

@article{f515f4f2d703419f989cd5fa41bf0870,

title = "Improved algorithm for single machine scheduling with release dates",

abstract = "This paper considered the single machine scheduling problem with unequal release dates so as to minimize total completion times. This problem was proved to be as an NP-hard problem. Traditional heuristics for the problem were analyzed, and then we presented an improved algorithm. A numerical example and its computational result were given. The performance of the algorithm was also analyzed by experiments and the experimental results show that the algorithm is more effective than the existing heuristics.",

keywords = "Heuristic algorithm, Release date, Single machine scheduling, Total completion times",

author = "Kai Li and Huawei Ma and Shanlin Yang",

year = "2008",

month = apr,

day = "25",

language = "英语",

volume = "19",

pages = "929--932",

journal = "Zhongguo Jixie Gongcheng/China Mechanical Engineering",

issn = "1004-132X",

publisher = "Chinese Mechanical Engineering Society",

number = "8",

}

TY - JOUR

T1 - Improved algorithm for single machine scheduling with release dates

AU - Li, Kai

AU - Ma, Huawei

AU - Yang, Shanlin

PY - 2008/4/25

Y1 - 2008/4/25

N2 - This paper considered the single machine scheduling problem with unequal release dates so as to minimize total completion times. This problem was proved to be as an NP-hard problem. Traditional heuristics for the problem were analyzed, and then we presented an improved algorithm. A numerical example and its computational result were given. The performance of the algorithm was also analyzed by experiments and the experimental results show that the algorithm is more effective than the existing heuristics.

AB - This paper considered the single machine scheduling problem with unequal release dates so as to minimize total completion times. This problem was proved to be as an NP-hard problem. Traditional heuristics for the problem were analyzed, and then we presented an improved algorithm. A numerical example and its computational result were given. The performance of the algorithm was also analyzed by experiments and the experimental results show that the algorithm is more effective than the existing heuristics.

KW - Heuristic algorithm

KW - Release date

KW - Single machine scheduling

KW - Total completion times

UR - https://www.scopus.com/pages/publications/44449121389

M3 - 文章

AN - SCOPUS:44449121389

SN - 1004-132X

VL - 19

SP - 929

EP - 932

JO - Zhongguo Jixie Gongcheng/China Mechanical Engineering

JF - Zhongguo Jixie Gongcheng/China Mechanical Engineering

IS - 8

ER -

Improved algorithm for single machine scheduling with release dates

Abstract

Keywords

Other files and links

Fingerprint

Cite this