Mathematical Programming and Heuristics for Scheduling Problems with Early and Tardy Penalties

International audience; The just-in-time concept was developed in Japan in the Toyota factory with the principal aim of eliminating waste at all levels. The importance of this method has resulted in the analysis of a wide range of scheduling problems within manufacturing. This chapter examines one such problem of minimizing early and tardy penalties on a machine. A section examines some specific examples of this type of scheduling problem and introduces three important properties for characterizing an optimal solution of the problem. Another section discusses several mathematical models for this problem and performs a comparative computational study on benchmark instances. This followed by separate sections that describe several existing heuristics for quickly generating a feasible solution to the problem and examine a range of metaheuristics proposed in the literature to obtain high-quality solutions. The final section presents conclusions and suggestions for future research concerning the problem.