期刊
OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE
卷 41, 期 2, 页码 299-304出版社
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.omega.2012.04.003
关键词
Scheduling; Mathematical programming model; Bin packing; Approximation algorithm; Tool change
资金
- National Key Basic Research and Development Program of China [2009CB320602]
- National Natural Science Foundation of China [60834004, 61025018]
- National Science and Technology Major Project of China [2011ZX02504-008]
- Science Foundation of Education Committee of Jiangxi for Young Scholars [GJJ11144]
- Doctor Foundation of East China Institute of Technology
This paper considers a variation of the classical single machine scheduling problem with tool changes. In the variation, two sets of jobs, namely special jobs and normal jobs, are considered. By special jobs, we mean that each special job must be processed within the first prefixed time units of a tool life. To solve the scheduling problem with small size and moderate size, we propose two mathematical programming models. To solve the scheduling problem with large size, we propose three sets of algorithms and focus on the performance of six algorithms based on the studies of a new bin packing problem. Worst-case analysis is conducted. Numerical experiment shows that each of the six algorithms can solve instances with up to 5000 jobs in about 0.5 s with an average relative error less than 4%. (C) 2012 Elsevier Ltd. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据