Several Scheduling Problems With Varying Processing Times

Scheduling problem is an important kind of combinatorial optimization problems.In traditional scheduling problems, it is assumed that the job processing times arefixed. In practice, however, the processing time of the job may depend on its positionin a schedule, its starting time or characteristics. In classical scheduling problems, alljobs should be accepted and processed on machines. However, manufacturers usuallyrefuse the jobs with longer processing time and smaller profit. As the same time, duedate assignment is also an important problem. In this paper, we study the aboveseveral scheduling problems. The main content is as following:The chapter1mainly introduces the definition of scheduling problems and thethree-field notation. In addition, we introduce the background of several varyingprocessing times of scheduling problems and our works in this paper.The chapter2mainly studies a single scheduling machine with problem due dateassignments and linear deteriorating, the objective is to find an optimal due date, theoptimal processing sequence of the jobs and the optimal start processing time tominimize the sum of due date assignment penalties and minimize the weightednumber of tardy jobs and the total of completion time.The chapter3mainly studies a due-date assignment problem with learning anddeteriorating effect and resource allocation on a single machine. The objective is tominimize a cost function containing earliness, tardiness, due date assignment, totalresource consumption and the total completion time.The chapter4mainly studies a uniform machine scheduling problem with simplelinear deterioration and rejection job. The objective is to minimize the sum of the totalcompletion time of the accepted jobs and the total rejection penalty of the rejectedjobs. The problem is NP-hard in the ordinary sense. We propose a fullpolynomial-time approximation scheme (FPTAS) for the case.