Minimization of maximum lateness in a flowshop learning effect scheduling with release dates

Abstract In fiercely competitive industries, customer satisfaction is a significant evaluation for a modern enterprise. Reduction of delivery lateness is an effective way to improve satisfaction and increase revenues. This study addresses a flowshop scheduling problem to optimize maximum lateness, where learning effect is introduced for each task, i.e., more familiar is a worker with a particular task, shorter is the execution time. For simulating the dynamic setting in an enterprise, each task has an individual release date. For this strongly NP-hard problem, exact and approximate algorithms are presented to satisfy different production scenes. An earliest-due-date- (EDD)-based heuristic is provided to obtain an approximate solution in a short time. Asymptotic analysis indicates the convergence of the EDD-based heuristic under marginal cost condition, which suggests that it can substitute the optimal schedule in sense of probability limit. The optimal solution is achieved by an effective branch and bound (B&B) algorithm for small-scale instances, where well-designed branching rules and lower bound improve its search ability. For medium-scale instances, a discrete artificial bee colony algorithm with hybrid neighborhood search mechanism is introduced to capture high-quality solutions. The performance of the metaheuristic is enhanced by EDD-based initialization and key-interval-based operators. A series of numerical simulations is implemented to highlight the advantages of the proposed algorithms.