Heuristic algorithm for uniform-machine scheduling with machine release times

Ying Ma; Shan Lin Yang; Da Wei Tang

Heuristic algorithm for uniform-machine scheduling with machine release times

Ying Ma
, Shan Lin Yang
, Da Wei Tang

Hefei University of Technology
Key Lab of the Ministry of Education for Process Control and Efficiency Egineering
University of Manchester

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

Abstract

This paper considers a problem of uniform-machine scheduling with machine release times to minimize makespan. Firstly, four properties of swapping jobs are proposed. Then, based on the properties, a heuristic algorithm is presented, which takes the LPT schedule as its initial solution and improves the solution by repeatedly swapping the jobs between two machines with the maximal and minimal makespan. Finally, computational results show that the presented heuristic is efficient and effective.

Original language	English
Pages (from-to)	2022-2030
Number of pages	9
Journal	Xitong Gongcheng Lilun yu Shijian/System Engineering Theory and Practice
Volume	32
Issue number	9
State	Published - Sep 2012
Externally published	Yes

Keywords

Longest processing time
Machine release times
Uniform-machine scheduling

Cite this

@article{b142b3f442b64ab1887419383a0097c6,

title = "Heuristic algorithm for uniform-machine scheduling with machine release times",

abstract = "This paper considers a problem of uniform-machine scheduling with machine release times to minimize makespan. Firstly, four properties of swapping jobs are proposed. Then, based on the properties, a heuristic algorithm is presented, which takes the LPT schedule as its initial solution and improves the solution by repeatedly swapping the jobs between two machines with the maximal and minimal makespan. Finally, computational results show that the presented heuristic is efficient and effective.",

keywords = "Longest processing time, Machine release times, Uniform-machine scheduling",

author = "Ying Ma and Yang, \{Shan Lin\} and Tang, \{Da Wei\}",

year = "2012",

month = sep,

language = "英语",

volume = "32",

pages = "2022--2030",

journal = "Xitong Gongcheng Lilun yu Shijian/System Engineering Theory and Practice",

issn = "1000-6788",

publisher = "Systems Engineering Society of China",

number = "9",

}

TY - JOUR

T1 - Heuristic algorithm for uniform-machine scheduling with machine release times

AU - Ma, Ying

AU - Yang, Shan Lin

AU - Tang, Da Wei

PY - 2012/9

Y1 - 2012/9

N2 - This paper considers a problem of uniform-machine scheduling with machine release times to minimize makespan. Firstly, four properties of swapping jobs are proposed. Then, based on the properties, a heuristic algorithm is presented, which takes the LPT schedule as its initial solution and improves the solution by repeatedly swapping the jobs between two machines with the maximal and minimal makespan. Finally, computational results show that the presented heuristic is efficient and effective.

AB - This paper considers a problem of uniform-machine scheduling with machine release times to minimize makespan. Firstly, four properties of swapping jobs are proposed. Then, based on the properties, a heuristic algorithm is presented, which takes the LPT schedule as its initial solution and improves the solution by repeatedly swapping the jobs between two machines with the maximal and minimal makespan. Finally, computational results show that the presented heuristic is efficient and effective.

KW - Longest processing time

KW - Machine release times

KW - Uniform-machine scheduling

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

M3 - 文章

AN - SCOPUS:84869145673

SN - 1000-6788

VL - 32

SP - 2022

EP - 2030

JO - Xitong Gongcheng Lilun yu Shijian/System Engineering Theory and Practice

JF - Xitong Gongcheng Lilun yu Shijian/System Engineering Theory and Practice

IS - 9

ER -

Heuristic algorithm for uniform-machine scheduling with machine release times

Abstract

Keywords

Other files and links

Fingerprint

Cite this