Journal
EXPERT SYSTEMS WITH APPLICATIONS
Volume 156, Issue -, Pages -Publisher
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.eswa.2020.113445
Keywords
Learning effect; Single-machine scheduling; Discrete differential evolution; Asymptotic analysis; Branch and bound
Categories
Funding
- National Science Foundation of China [61873173, 61873328]
- National Science Fund for Distinguished Young Scholars of China [61525304]
- Ministry of Science Technology of Taiwan [MOST 108-2911-E-035-500, MOST 108-2410-H035-046]
Ask authors/readers for more resources
Multi-variety and small-batch productions are usually undertaken by skilled workers instead of an automatic assembly line because of economic cost consideration. In the production process, a worker's familiarity to an operation influences the length of task execution time. An interesting phenomenon called learning effect has become a trending research topic. This study investigates a learning effect scheduling model on a single machine system, in which the learning effect is position-dependent and each task is released at different dates. Two optimal criteria are individually discussed: one is total k-power completion time, and the other is maximum lateness. Both problems are NP-hard, therefore, effective algorithms are provided to handle different scale problems within an appropriate CPU time. The heuristic algorithms, namely, shortest processing time available and earliest due date available, are introduced to achieve feasible schedules for large-scale instances, and their asymptotic optimality is proven given that the problem scale tends to infinity. The two heuristics can thus serve as optimal algorithms in mass production. For small-scale instances, a branch and bound algorithm is presented to achieve the optimal solution, where a release-date-based branching rule and preemption-based lower bounds eliminate as many invalid nodes as possible. For medium-scale instances, an evolutionary-based metaheuristic algorithm, namely, discrete differential evolution, is utilized to seek high-quality solutions, in which the initial population and crossover operator are well-designed to enhance its performance. A number of random experiments demonstrate the superiority of the proposed algorithms. (C) 2020 Elsevier Ltd. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available