Scheduling Problems With Learning And Deterioration Effect And Availability Constrain

In some real production situations, the processing time of a job changes due toeither job deterioration over time or machine/worker`s learning through experiences.In this model, the processing times of jobs are related with their positions and startingtimes in a sequence; Moreover, the machine could be unavailable for a specifiedperiod by periodic machine breakdown or maintenance activity. As a result, theprocessing time of a given job is shorter if it is scheduled later in the productionsequence, the phenomenon is known as learning effect in the literature. Theprocessing time of a given job is longer if it is scheduled later in the productionsequence, the phenomenon is known as deteriorating effect in the literature.Machine may become unavailable due to a machine breakdown or preventivemaintenance during the scheduling period, the phenomenon is known as availabilityconstraint in the literature. In this paper, we consider three aspects of above, thespecific content as follows:1、For the machine unavailability in the common case at any time problem of thesingle machine, we consider two aspects:(1) When the processing time of a job with learning and deteriorating effect, westudy the problem that the objective is to minimize the total completion time.(2) When the processing time of a job with learning and deteriorating effect, thejob processing times and their weightes are disagreeable, we study the problem thatthe objective is to minimize the total weightied completion time.The upper problems are both NP-hard. In this paper, we propose the optimalsolution properties of two different objective functions, present the differentpseudopolynomial algorithms, and analyze the complexity of algorithms, respectively.Finally, we show the efficiencies of the proposed algorithms by numeral examples.2、For the only one machine have availability constraint in the common case atany time problem of two parallel machines, we consider two aspects and show theoptimal solution properties and provide pseudopolynomial algorithm, analyze thecomplexity of algorithm.3、For the problem of the processing time of a job with an exponential learning and availability constraint, we consider the cases of single machine and two parallelmachines. The objective function is the total completion time. The dynamicprogramming algorithms are provided for the machine maintenance in the commoncase at any time, respectively, and analyze the complexity of algorithms. We showthe efficiency of the proposed algorithm by corresponding numeral example. For themaintenance case of machine at zero time, a polynomial optimal algorithm is given bytransforming to an assignment problem.