Minimizing the makespan in a single machine scheduling problem with a time-based learning effect |
| |
Authors: | Wen-Hung Kuo |
| |
Affiliation: | a Department of Industrial Engineering and Technology Management, Da-Yeh University, Chang-Hwa, Taiwan 515, R.O.C. b Department of Information Management, National Formosa University, Yun-Lin, Taiwan 632, R.O.C. |
| |
Abstract: | Both the building cost and the multiple-source routing cost are important considerations in construction of a network system. A spanning tree with minimum building cost among all spanning trees is called a minimum spanning tree (MST), and a spanning tree with minimum k-source routing cost among all spanning trees is called a k-source minimum routing cost spanning tree (k-MRCT). This paper proposes an algorithm to construct a spanning tree T for a metric graph G with a source vertex set S such that the building cost of T is at most 1+2/(α?1) times of that of an MST of G, and the k-source routing cost of T is at most α(1+2(k?1)(n?2)/k(n+k?2)) times of that of a k-MRCT of G with respect to S, where α>1, k=|S| and n is the number of vertices of G. |
| |
Keywords: | Scheduling Time-based Learning effect Single machine |
本文献已被 ScienceDirect 等数据库收录! |
|