Single Machine Scheduling Problem With Machine Maintenance Activities And Deteriorating Effect Of Jobs

In recent years,machine scheduling problems have gained enormous attentions theoretically and practically.They have been applied in various fields such as engineering,computer science as well as management science,especially in manufacturing and hospitality industry.Machine scheduling basically aims to study how to set up accurate and concise models for problems of production planning and how to analyze those models,by using existing theories of mathematics or proposing artificial and intellectual algorithms in order to optimize the objective function and to satisfy the needs of a factory(company)as well as the end consumers(minimizing the production cost,maximizing the profits,minimizing the flowtime/makespan as well as minimizing the total tardiness).However,traditional models of machine scheduling did not consider the availability and the reliability of a machine.Instead,it mostly assumed that machine is available during the whole process of manufacturing.At the same time,it is also noted that traditional models of machine scheduling focus more on constant processing time of a job for tractability.Nevertheless,in reality,the condition of a machine can affect manufacturing in various degrees: sometimes a machine breaks down or suffers from deterioration because of wear and tear,leading to variable job's processing time: a job is subjected deteriorating effect.Therefore,the hypotheses of constant availability of a machine or constant jobs' processing times are being challenged.Based on the above-mentioned background and assumptions,this paper set up two models of machine scheduling: single machine scheduling problems with machine maintenance and deteriorating effect of jobs.Firstly,it suggests a single machine batch scheduling problem with deteriorating effect of jobs and periodic machine maintenance activities: a job is suffered from time-dependent overlapping deteriorating effect,which is related to the actual processing time of the jobs(a job's actual processing time is positively relevant to the total actual processing time of the jobs processed before it).At the same time,maintenance activities are mandatory before/after a batch of jobs finish being processed and the maintenance time for the machine is relevant to the flow time of a batch.The maintenance time for the machine deteriorates(increases),too.Next,according to the theory of system reliability and constraints,this paper came up with a single machine scheduling problem with deteriorating effect of jobs and stochastic machine maintenance activities: Jobs are still suffered from time-dependent overlapping deteriorating effect and the maintenance behaviors of the machine are decided by the machine reliability.The maintenance activities in machine reliability include preventive maintenance and corrective maintenance.Corrective maintenance is implemented after a machine randomly breaks down so as to make the machine restore to a certain condition for continuing processing the jobs.While,the preventive maintenance is carried out before each job is processed or finished processing for improving the reliability of the machine and reduce the risks of failure as much as possible.As for the single machine batch scheduling problem with deteriorating effect of jobs and periodic machine maintenance activities,it analyzes the optimal schedule within the batch and between the batches.What is more,it proposed a polynomial algorithm for deriving the optimal schedule and minimizing the makespan.As for the single machine scheduling problem with deteriorating effect of jobs and stochastic machine maintenance activities,this paper started by analyzing the special cases of this problem in order to obtain the optimal conditions for the optimal schedule of jobs.Then,it proposed two important theorems.Based on the theorems,it suggested utilizing the method of integration partition to eliminate the redundancy of some feasible solutions.Furthermore,it made use of the properties of the problem in order to propose two different heuristics combined with genetic algorithm and greedy algorithm.At last,it tested the efficiency and effectiveness of those algorithms with MATLAB.Results showed that 1)the effectiveness and the efficiency of the proposed heuristic algorithms are influenced by the number of jobs,the deteriorating effect of jobs as well as the jobs' normal processing times.2)When the number of jobs is smaller,the solution obtained by the heuristics is the same as the optimal solutions gained by modified enumeration.3)When the number of jobs is larger,the solution obtained by the heuristics are better.What is more,the maintenance policies obtained by the heuristics are much more reliable.