SINGLE-MACHINE SCHEDULING PROBLEMS WITH GENERAL BREAKDOWNS, EARLINESSAND TARDINESS COSTS

In this paper we consider single machine scheduling problems with a co mmon due-date for all jobs, arbitrary monotone earliness and tardiness costs and arbitrary breakdown and repair processes. We show that the problem is equivalent to a deterministic one without breakdowns and re pairs and with an equivalent cost function of a Sob's completion time. A V-shaped schedule without idle times is shown to be optimal, if thi s equivalent cost function is quasi-convex. Conversely, we show that a V-shaped schedule may fail to be optimal if the property does not app ly. We derive general conditions for the earliness and tardiness cost structure and repair and breakdown processes under which the equivalen t cost function is quasi-convex, When a V-shaped schedule is optimal, an efficient (though pseudo-polynomial) algorithm can be used to compu te an optimal schedule.