A Branch And Bound Algorithm For Scheduling With Two Kinds Of Special Jobs On Single Machine

Scheduling problems play increasing important roles in solving complicated problems ap-pearing in the fields of economy, management, engineering, military affairs and society etc. Thispaper deals with problems of scheduling n jobs on a single machine, the objective is to maxi-mize the remaining value of all jobs. This problem is motivated from the real-life application,such as movie scheduling, remanufacturing of high-technology products, web object transmis-sion, and banner advertising.We focus on the following two kinds of jobs. Deteriorating jobs have been defined in theliterature as jobs whose processing time is an increasing over its starting time. Deterioratingvalues of jobs we mean that the value of jobs decrease over completion time. Combined withabove two kinds of jobs, we discuss the first kinds of special job whose value is a power func-tion of its completion time, and its processing time is function of its starting time, where thefunction is pj=bj(a+bt)(bj, a, b>0), t is job’s starting time. The second kind of specialjob’s processing time is constant, and the value of jobs is also a power function of its completiontime.For solving this two kinds of special job’s scheduling problems on single machine, branchand bound method is developed, which using a sub-optimal solution of a heuristic algorithm asan initial solution and a upper bound to search for an optimal solution in a solution tree, thesolution tree is got by cutting those unnecessary branches which will not contain the optimal so-lution. Finally, we construct and experimentally test branch and bound algorithm and comparethe results(in terms of computer time needed for the application)to those of complete enumera-tion to demonstrate the effectiveness of the algorithm.