Machine Scheduling Problems With The Nonconstant Processing Times

Scheduling is an important combinatorial optimization problem. In the classicalscheduling problems it is assumed that the processing times of jobs are constant values.However, there are many situations where the processing time of the job depends on itsstarting time or its position in the sequence. From this, the new classes of schedulingproblems emerged. The new classes of scheduling problems are more complex thanclassical scheduling problems, most of which are NP-hard problems. Considering therequirement of practical application, the cases of new classes of scheduling problemswhich are polynomial complexity algorithms are very necessary. On one side thepolynomial algorithms can be used to solve some problems, on other side the algorithmscan be considered as approximation algorithms of other problems.Based on modern scheduling problem, we study some scheduling problems whereits processing time is not constant. The basic idea of research for these schedulingproblems: firstly, developing models according to the proposed problems; secondly,considering the complexities of them. Most of them are NP-hard, so we givepolynomial algorithms for the special solvable cases and develop effective heuristicsand analyze their worst-case error bound or give dynamic programming algorithm forthe general cases.This paper studies some problems, as following:⑴The scheduling problems with sum-of-processing-time based learning effect,We consider four learning effect models as following: general learning effect,sum-of-processing-time based exponential or logarithmic learning effect, groupscheduling problems with learning effect. For single-machine scheduling problems, themakespan problem and the total completion time problem without group technologyremain polynomial time algorithms by SPT rule. The total completion time problemcan be obtained to a polynomial optimal solution under group technology assumption,if the number of jobs in each group is the same. In addition, we also show that the totaltardiness problem and the maximum lateness problem have a polynomial optimalsolution under certain cases. The flowshop problems with learning effect are morecomplex. For two cases: the processing times on all the machines and dominantmachines, the makespan problem and the total completion time problem have polynomial time algorithms, respectively. We also consider minimizing the makespanand minimizing the total completion time problems with aging effect. We discuss thethree cases:0＜a₁≤1，1＜a₁＜M，a₁≥M.If the aging index is1＜a₁≤M, theoptimal solution of the problem is open.⑵Time-dependent scheduling and scheduling problems with learning effect.When arrive time of jobs depends on its resource allocation, we analyze minimizingmakespan problem and minimizing resource consumption problem. The optimalalgorithms are presented for the problems to minimize the makespan with the totalresource consumption constraints. Then we propose an optimal solution for theproblems to minimize the total resource consumption with the makespan constraints ingiven sequence. For time-dependent and learning effect problems, we show that themakespan and total completion time problem have polynomial time algorithms, but totalweighted completion time, maximum lateness, discounted total weighted completiontime and number of tardiness jobs do not exist a polynomial time algorithm. In order ofsolving the problems approximately, we can use classical algorithms as a heuristicalgorithm for general problem, the performance of the heuristic is evaluated by itsworst-case error bound. We also show that several special cases of these problemsremain polynomial solvable in the proposed models. A polynomial dynamicprogramming algorithm is presented to solve the reworkable（RW） problem. Ifcompletion time of jobs and size in each batch are agreeable, we give a polynomial timealgorithm. In conditional, we study some group technology problems with deterioratedjobs and learning effect.⑶Machine scheduling problems with respect to due date.For common due window, we analyze the different deteriorated rate problem andthe same deteriorated rate problem. The two problems can be formulated as assignmentproblem. Then we discuss common due window in rate-modify activity or out, and wegive matching algorithms and their computational complexity. By CON assignmentmethod and SLK assignment method, we study due date assignment problems wherethe objective is the cost of changing the due dates, a possible penalty function for thetotal early jobs and the total penalty for discarding jobs.⑷Rescheduling problems.In this chapter, our main contribution is introduced the concept of deteriorated jobsand learning effect into rescheduling fields. We consider the total tardiness problems under sequence disruption and time disruption. Furthermore, we also propose thepolynomial time algorithms or pseudo-polynomial time algorithms or dynamicprogramming algorithms.The thesis presents the following original ideas:1) By the boot time of the Vista/WIN7system and the proficiency of computeroperators, we propose a new model which considers the human and themachine learning effects at the same time. This model has more general anduniversal. In proposed scheduling models with learning effect, the actualprocessing time of a given job may drop to zero precipitously or be very large.We present exponential or logarithmic based learning models to improve theinsufficient of the previous models.2) Customers often provide orders by the actual production capacitymanufacturers, so it is very realistic and urgent that we consider the problemswith arrive times and resource allocations. We firstly put forward that thearrival time of a job is the decreasing function of resource consumption, theresource consumption as a goal or constraints is analyzed.3) Based on the actual production and requirements of reverse logisticsenterprises, we firstly address the scheduling problem of scheduling work andrework with deteriorating and learning effect. A polynomial dynamicprogramming algorithm is presented to solve these problems.4) We groundbreakingly present the rescheduling problems where its processingtime is not constant.