Parallel-batching scheduling with nonlinear processing times on a single and unrelated parallel machines
- PDF / 1,981,025 Bytes
- 23 Pages / 439.37 x 666.142 pts Page_size
- 62 Downloads / 243 Views
Parallel-batching scheduling with nonlinear processing times on a single and unrelated parallel machines Min Kong1,2 · Xinbao Liu1,2 · Jun Pei1,2,3 · Panos M. Pardalos3 · Nenad Mladenovic4 Received: 16 December 2017 / Accepted: 4 September 2018 © Springer Science+Business Media, LLC, part of Springer Nature 2018
Abstract Parallel-batching processing and job deterioration are universal in the real industry. Scholars have deeply investigated the problem of parallel-batching scheduling and the problem of scheduling with deteriorating jobs separately. However, the situations where both parallelbatching processing and job deterioration exist simultaneously were seldom considered. This paper studies the parallel-batching scheduling problem with nonlinear processing times on a single machine, and proposes several structural properties and an optimal algorithm to solve it. Based on the above properties and optimal algorithm for the single machine setting, we further study the problem of parallel-batching scheduling with nonlinear processing times under the unrelated parallel machine setting. Since the unrelated parallel machines scheduling problem is NP-hard, a hybrid SFLA-VNS algorithm combining Shuffle Frog Leap Algorithm (SFLA) with Variable Neighborhood Search Algorithm (VNS) is proposed. Computational experiments and comparison are finally conducted to demonstrate the effectiveness of the proposed algorithm. Keywords Parallel-batching · Scheduling · Nonlinear processing times · Meta-heuristic algorithm
1 Introduction The parallel-batching scheduling problem was first addressed by Lee et al. [1]. Recent two decades have witnessed extensive research of the parallel-batching scheduling problem. The parallel-batching processing machines exist widely in practice, such as composite manufac-
B B
Min Kong [email protected] Jun Pei [email protected]
1
School of Management, Hefei University of Technology, Hefei 230009, China
2
Key Laboratory of Process Optimization and Intelligent Decision-Making of Ministry of Education, Hefei 230009, China
3
Center for Applied Optimization, Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL 32611, USA
4
Mathematical Institute, Serbian Academy of Sciences and Arts, Beograd 11001, Serbia
123
Journal of Global Optimization
turing [2], semiconductor burn-in operations [3], and metal working [4]. In addition, many parallel-batching scheduling problems are NP-hard, even in the single machine environment [5, 6], thus further study is also of great theoretical significance [7–10]. In many parallel-batching scheduling problems, the job’s processing time is usually considered as a constant, and it is independent of its processing position or starting time. However, there are various real-life situations where the job’s processing time may be influenced by machine aging effect or the fatigue of the workers. As such, the actual processing time of a job is usually modeled as an increasing function of its starting time. Scheduling problem with deteriorati
Data Loading...
