Scheduling Problem With Varying Processing Times And Rejection Jobs

Scheduling problem is an important problem in combinatorial optimization. Inthe classical scheduling problem, all jobs are accepted and the processing time of ajob is a fixed constant. However, in the real word, jobs may be rejected and theprocessing time of the job may depend on its position in a schedule and its startingtime or resource allocation obtained.This thesis consists of five parts. Firstly, we introduce some backgroundinformation of scheduling problems and our main results.In the second chapter, we consider a due-window assignment problem withlearning and deteriorating effect and resource allocation on a single machine. All jobshave a common due-window. Jobs completed within the due-window incur nopenalties, other jobs completed before or after the due-window incur either earlinessor tardiness penalties. Job’s processing times are defined by functions of their startingtimes, positions in the sequence and resource allocation to it. The objective is todetermine the optimal due-window location and size, the optimal sequence and theoptimal resource allocation to minimize a total costs based on earliness, tardiness,due-window size, due-window location and resource consumption. We show that theproblem is polynomial time solvable, and provide an optimization algorithm.In the third chapter, we consider a single machine scheduling problem withrejection jobs and a machine non-availability interval. Jobs have different releasedates and weights, the weight of a job equals to its processing time. The objective is tominimize the sum of the total special weighted completion times of the accepted jobsand the total rejection penalty of the rejected jobs. The problem is NP-hard in theordinary sense. We propose a fully polynomial-time approximation scheme.In the forth chapter, we consider scheduling problem with deteriorating jobs andrejection on uniform machines. Each job’s processing time is a linear non-decreasingfunction of its start time. A job can be rejected by paying a penalty cost. The objectiveis to minimize the sum of makespan of the accepted jobs and the total rejectionpenalty of the rejected jobs. We propose a fully polynomial-time approximationscheme, which proves that the problem is NP-hard in the ordinary sense. The last part of the paper summarizes the whole dissertation, and problems thatneed to be studied further are given out.