Common Due-Window Assignment and Group Scheduling with Position-Dependent Processing Times

摘要

This paper investigates a single-machine scheduling problem involving both the due-window assignment and position-dependent processing times under a group technology environment. By position-dependent processing times, we mean that the processing time of a job is dependent of its processing position in the job sequence within the group it belongs to. A setup time is incurred whenever the single machine transfers job processing from a group to another group. Each group is assigned an assignable common due-window. A job completed earlier (respectively, later) than the common due-window of the group it belongs to will incur an earliness (respectively, tardiness) penalty. The objective is to determine the optimal group sequence, the optimal job sequence, and the optimal due-window assignment so as to minimize the total cost including the earliness and tardiness (or weighted number of tardy jobs) penalties, black and the due-window starting time and due-window size costs. We show that both the problems can be solved in polynomial times.