Nowadays scheduling problems have wide application in many production systems and services. In many of them processing time are constant and predetermined. This consumption is true in some cases but because machines and tools Depreciate and their efficiency reduce during time, this consumption cannot be true in all cases. In addition, in some industries like steel industry job’s Delay for process result in longer processing time. These kinds of jobs are introduced as deteriorating jobs, so a job is deteriorating whenever its processing time is not constant and is dependent to scheduled jobs. In the other words a job which is process later needs more time to process. Job processing time may depend on three factors, job’s start time, its position or the sum of basic process time for scheduled job. In this thesis single and multiple machines scheduling with deteriorating consumption is studied. A general dir=rtl Single machine scheduling problem with piecewise linear deteriorating consumption and minimizing number of tardy jobs as objective function in which job’s processing times is a non-decreasing function based on the job starting time. All jobs have different deteriorating rate. Because the same studies haven’t seen yet in the literature, the problem complexity is examined and demonstrated that it is an NP-hard problem. So for solving this problem an exact approach based on branch and bound algorithm which considers some theory and lemma, three lower bound and dominance rules, is presented. A heuristic algorithm is also presented with O(n 2 ) and is use as upper bound for the problem. Computational results for 1840 problems show that problems with 28 jobs can be solved in all series and in some series this number is higher. In general the branch and bound algorithm can solve 85.4% of examples optimally which shows the efficiency of the algorithm. In addition the average of optimal answer to heuristic answer ratio with the number no tardy jobs as objective functio is less than 1.08, and this number is less than the result of algorithm proposed in researches with the objective of minimizing number of tardy jobs. Because of high efficiency of the heuristic algorithm, problems with higher job size are solved and results are presented. Seven specific cases are also considered and demonstrated that all of them are NP-hard. Changes occur in branch and bound trend and heuristic algorithm are presented and in each case results and the efficiency of method are demonstrated separately.
