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

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.

Automated summary

In fiercely competitive industries, customer satisfaction is crucial for modern enterprises, and reducing delivery lateness is an effective strategy to achieve this. This study focuses on optimizing maximum lateness in flowshop scheduling, introducing learning effects and individual release dates for tasks. Exact and approximate algorithms are proposed to handle different production scenarios, and heuristic methods and metaheuristic algorithms are employed to obtain high-quality solutions efficiently. Performance enhancements are achieved through various techniques, including asymptotic analysis, branch and bound algorithm, and discrete artificial bee colony algorithm with hybrid neighborhood search. Numerical simulations demonstrate the advantages of the proposed algorithms in addressing the scheduling optimization problem.