Minimize Total Completion Time On A Single Machine Scheduling Problem With Learning Effect Consideration

The learning activities will have a significant influence on production processing if there has an involvement of humans in scheduling environments. Hence, it is more reasonable to take the learning effects into consideration on some production scheduling problem. On the other hand, the release times, plays an important role in developing production plan, has a close relationship with the efficiency of the entire production activities. For example, jobs can be form a batch to be processing simultaneously in Wafer fabrication with the presence of unequal release time. It is sometimes advantageous to form a non-full batch due to special long waiting time, while in other situations it is a better strategy to wait for future job arrivals in order to increase the fullness of the batch. Therefore, it has theoretical and practical significance to take both learning effect and unequal release time into consideration in some scheduling production.However, research with learning and ready times is limited, which either based on position-dependent or sum-of-normal-time dependent learning effect. Motivated by this, in this paper, a single machine scheduling problem with actual time-dependent learning effect and unequal release time consideration is investigated where the objective is to minimize the total completion time.Firstly, a nonlinear integer programming model is formulated for this problem, which will be used to obtain the solutions for small size problems through the ILOG CP software. Then, two dominance rules are developed by pairwise interchange technique. Then a branch-and-bound (B&B) algorithm incorporating with two dominance properties and two lower bounds is developed to obtain solutions for small size problems. Finally, a hybrid particle swarm optimization (HPSO) algorithm combined with the dominance rules, genetic operators and simulated annealing algorithm is proposed since this problem is NP-hard.In order to exam the performance of the proposed branch-and-bound algorithm and hybrid particle swarm optimization algorithm, two experiments are developed based on the job size. The first experimental results demonstrate that the proposed branch-and-bound algorithm has a better performance than CP in small size problems. The HPSO algorithms can even obtain optimal solutions for some situations in small problems. In addition, the second experimental results shows that the proposed HPSO algorithm outperform the benchmark algorithms in the literature and the advantage becomes more obvious with the number of jobs.