Scheduling Problems with Optimal Due Interval Assignment Subject to Some Generalized Criteria

The paper deals with two problems of scheduling jobs on identical parallel machines, in which a due interval should be assigned to each job. Due interval is a generalization of well known classical due date and describes a time interval, in which a job should be finished. In the first problem, we have to find a schedule of jobs and a common due interval such that the sum of the total tardiness, the total earliness and due interval parameters is minimized. The second problem is to find a schedule of jobs and an assignment of due interval to all jobs, which minimize the maximum of the following three parts: the maximum tardiness, the maximum earliness and the due int erval parameters. We proved that the considered problems are NP-hard and outlined some methods how to solve them approximately as well as optimally.