Minimizing total weighted error for imprecise computation tasks and related problems

Scheduling problems with due date related objectives are usually concerned with penalties such as the weighted number of late jobs (i.e., Σw_jU_j), or the weighted amount of time between the completion time of the late job and its due date (i.e.,Σw_j T_j). In some applications, however, it is more meaningful to consider penalties involving the weighted number of tardy units (i.e., the weighted number of time units that are late), regardless of how late these units are. This is the case, for example, in a computerized control system, where data are collected and processed periodically. Any data that are not processed before the arrival of the next batch will be lost, and the lost data will have a negative effect on the accuracies of the calculations that are used to control the real-time process. Another example can be found in processing perishable goods, such as harvesting. In this case, jobs represent different stretches of land that need to be harvested. Because of differences in climate and soil conditions and crop culture, the different stretches need to be harvested during different time periods. Crops will perish after its due date, which will cause financial loss. In this application, minimizing the weighted number of tardy units is more meaningful than the other objectives.