Volume 55, 2021Regular articles published in advance of the transition of the journal to Subscribe to Open (S2O). Free supplement sponsored by the Fonds National pour la Science Ouverte
|Page(s)||S253 - S269|
|Published online||09 February 2021|
Optimizing batch-processing operations with batch-position-based learning effects
Anhui University of Traditional Chinese Medicine, Hefei, 230012, P.R. China.
* Corresponding author: firstname.lastname@example.org
Accepted: 10 November 2019
Motivated by applications in porcelain-making companies, we consider a type of optimization problems for batch-processing operations. In production, a single batch-processing machine with a fixed capacity is used to process jobs. Several jobs can be processed together if their total size is no more than the machine capacity. Batch-position-based learning effects are considered because workers become skillful gradually after they perform the processing task repeatedly. The actual processing time of a batch is a decreasing function of its position in production. The objective is to minimize makespan and we consider three different problems. In the first problem, jobs have identical sizes and we present an algorithm which can find optimal solutions in polynomial time. In the second problem, jobs have identical processing times and we show the problem is NP-hard in the strong sense. We propose an approximation algorithm with an absolute performance guarantee of 1.5 and asymptotic performance guarantee of 1.223. In the third problem, jobs have non-identical sizes and processing times simultaneously. We propose an algorithm with an absolute and asymptotic performance guarantee of 2. Besides, we present the evolution of the performance guarantee and provide managerial insights for decision makers of manufacturing companies.
Mathematics Subject Classification: 90C97
Key words: Optimization / learning effects / batch processing / scheduling / heuristics
© EDP Sciences, ROADEF, SMAI 2021
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.