Properties’ research of the scheduling problem for a single machine by minimizing the total earliness of tasks with the condition of the schedule feasibility
We consider a scheduling problem of independent tasks execution with arbitrary durations and various due dates on a single machine by minimizing the total earliness and finding the maximum startup time of the tasks in a feasible schedule. The exact polynomial algorithms are proposed for particular cases of the task, for the general case an upper estimate of the deviation from the optimum quality index is determined.