The single machine scheduling problem with setup times under an extension of the general learning and forgetting effects

Abstract

This paper addresses the optimization of a single machine scheduling problem with additional constraints which are sequence-independent setup times and time-dependent 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.