Scheduling parallel machine problem under general effects of deterioration and learning with past-sequence-dependent setup time: heuristic and meta-heuristic approaches

摘要

This study investigates an identical parallel machine scheduling problem with past-sequence-dependent setup times and general effects of deteriorating and learning. The actual job processing time on each machine is defined by a two-element function of the normal processing times of the preprocessed jobs and its scheduled position on the same machine. Moreover, the job setup time on each machine is a function of the actual processing times of the preprocessed jobs on the same machine. A novel mixed-integer programming model is developed to satisfy the goal of minimizing total completion time. Due to the NP-hard characteristic and intractability of the problem, three efficient methodologies including a heuristic algorithm (HA), a genetic algorithm (GA) with an enhanced exploration ability and an ant colony optimization (ACO) combined with a new stochastic elitism strategy are designed to find optimal/near-optimal solutions within an appropriate period of time. The effectiveness and efficiency of the presented model and the proposed algorithms are verified by computational experiments. The computational results indicate that the suggested algorithms are effective and executable approaches to generate solutions as good as optimal solution in the small-sized problems. Also, the ACO statistically outperformed the HA and GA in the medium- and large-sized problems.