The single machine scheduling problem with setup times under an extension of the general learning and forgetting effects
- PDF / 542,419 Bytes
- 17 Pages / 439.37 x 666.142 pts Page_size
- 13 Downloads / 221 Views
The single machine scheduling problem with setup times under an extension of the general learning and forgetting effects Settar Mu¸stu1
· Tamer Eren1
Received: 17 August 2019 / Accepted: 1 September 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract This paper addresses the optimization of a single machine scheduling problem with additional constraints which are sequence-independent setup times and timedependent learning and forgetting effects. The considered objective function is to minimize the maximum completion time (makespan). We define a bivariate general learning and forgetting model consisting of two independent variables which are the sum of normal processing times of previous jobs in the schedule and the setup time of the present job. We demonstrate some global properties of an optimal schedule and prove that the problem is ordinary NP-hard by means of a polynomial transformation from a known decision problem to the decision version of the considered problem. Furthermore, we propose an integer non-linear programming model and a dynamic programming model which can be executed in pseudo-polynomial time. Keywords Learning effect · Forgetting effect · Setup time · Complexity · Pseudo polynomial time algorithm
1 Introduction Scheduling problems arise due to the use of production resources by a few products. The decision-making process requires a feasible appointment of specific time intervals to users by considering the existing constraints [1]. In this case, the assumption of unvarying processing times negatively affects the precision of the decision-making process since an increment in the efficiency of workers provides a reduction in processing times. It means that workers improve their skills and gain experience by
B
Settar Mu¸stu [email protected] Tamer Eren [email protected]
1
Department of Industrial Engineering, Ostim Technical University, Ankara, Turkey
123
S. Mu¸stu, T. Eren
repeatedly doing the same task. This phenomenon is known as the learning effect and it was approved by the scheduling literature [2–4]. The learning curve, also known as the manufacturing progress function, represents the improved efficiency obtained from repeating an operation [5]. However, there is an inverse phenomenon known as the forgetting effect which can occur due to several reasons in the production process. Since learning and forgetting are important issues in production planning and scheduling as well as in pricing and cost estimating, there is a need for a better understanding of the forgetting effect [6]. Badiru [7] classified the forgetting effect in three reasons which are (a) intermittently occurrence of forgetting throughout scheduled production breaks, (b) random or predictable occurrence of forgetting that might depend on machine breakdowns, and (c) continuously occurrence of forgetting due to some natural process like ageing. Furthermore, another reason for forgetting is disruption caused by changes in the production environment such as job types, tools, plant layout, wor
Data Loading...
