Group scheduling and job-dependent due window assignment based on a common flow allowance

• We consider group scheduling and job-dependent due window assignment.
• Each job is assigned an individual due window based on a common flow allowance.
• The goal is to find the optimal sequence for both the groups and jobs.
• Polynomial time optimal algorithm is proposed.

We study a single-machine group scheduling and job-dependent due window assignment problem in which each job is assigned an individual due window based on a common flow allowance. In the group technology environment, the jobs are divided into groups in advance according to their processing similarities and all the jobs of the same group are processed consecutively in order to improve production efficiency. A sequence-independent machine setup time precedes the processing of the first job of each group. A job completed earlier (later) than its due window will incur an earliness (tardiness) penalty. Our goal is to find the optimal sequence for both the groups and jobs, together with the optimal due window assignment, to minimize the total cost that comprises the earliness and tardiness penalties, and the due window starting time and due window size costs. We give an O(n log n)time algorithm to solve this problem.