A Truncated Sum of Processing‐Times–Based Learning Model for a Two‐Machine Flowshop Scheduling Problem

Scheduling with learning effects has gained increasing attention in recent years. A well‐known learning model is called “sum‐of‐processing‐times‐based learning” in which the actual processing time of a job is a nonincreasing function of the jobs already processed. However, the actual processing time of a given job drops to zero precipitously when the normal job processing times are large. Moreover, the concept of learning process is relatively unexplored in a flowshop environment. Motivated by these observations, this article addresses a two‐machine flowshop problem with a truncated learning effect. The objective is to find an optimal schedule to minimize the total completion time. First, a branch‐and‐bound algorithm incorporating with a dominance property and four lower bounds is developed to derive the optimal solution. Then three simulated annealing algorithms are also proposed for near‐optimal solution. The experimental results indicated that the branch‐and‐bound algorithm can solve instances up to 18 jobs, and the proposed simulated annealing algorithm performs well in item of CPU time and error percentage. © 2011 Wiley Periodicals, Inc.