Most of the researches about scheduling problems are devoted to different assumptions and shop environments, and few number of them are about developing effective objective functions. This thesis proposes a general performance measure for scheduling problems that includes piecewise linear earliness and tardiness penalties as well as a delivery due window. This performance measure has some applications in real world situations and is convertible to various objective functions through adjusting its parameters. Then, eight new objective functions are proposed and some applications and the way of deriving them from proposed measure are described. Biased tardiness and tardy/lost penalty are two of the new functions proposed in this thesis and used in single machine environment. For biased tardiness penalty, the complexity of the problem is proved on a single machine and some approximation algorithms, dynamic programming algorithms and FPTASs are introduced. Tardy/Lost is also studied by proving its complexity and developing mathematical model, heuristic and approximation algorithms, dynamic programming and branch and bound algorithms as well as some FPTASs. Scheduling of parallel jobs on grid systems is considered as a special case for the proposed measure. The measure is adjusted for being applied in SLA contracts and a new heuristic algorithm based on simulated annealing is developed
