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

科研成果: 期刊稿件 › 文章 › 同行评审

摘要

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.

源语言	英语
页（从-至）	2022-2030
页数	9
期刊	Xitong Gongcheng Lilun yu Shijian/System Engineering Theory and Practice
卷	32
期	9
出版状态	已出版 - 9月 2012
已对外发布	是

其它文件与链接

链接到 Scopus 的出版物

引用此

@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

摘要

其它文件与链接

学术指纹

引用此