Single-Machine Scheduling Problems with a Sum-of-Processing-Time-Based Learning Function. (17th January 2010)

• Record Type: Journal Article
• Authors: Zhang, Xingong; Yan, Guangle
• Other Names: Kang Liying Academic Editor.
• Is Part Of: International journal of combinatorics. Volume 2009(2009)
• Publication Date: 2010-01-17
• Subjects: Combinatorial analysis -- Periodicals; Combinatorial analysis; Periodicals; Electronic journals; 511.605
• DOI: 10.1155/2009/624108
• Languages: English
• ISSNs: 1687-9163

Abstract

Abstract : Recently, learning scheduling problems have received increasing attention. However, the majority of the research assume that the actual job processing time is a function of its position. This paper deals with the single-machine scheduling problem with a sum-of-processing-time-based learning effect. By the effect of sum-of-processing-time-based learning, we mean that the processing time of a job is defined by total normal processing time of jobs in front of it in the sequence. We show that the single-machine makespan problem remains polynomially solvable under the proposed model. We show that the total completion time minimization problem fora ≥ 1 remains polynomially solvable under the proposed model. For the case of0 < a < 1, we show that an optimal schedule of the total completion time minimization problem isV -shaped with respect to normal job processing times.