Research On Production Scheduling Models And Optitmization Algorithms With Controllable Time

The scheduling theory for the procession sequencing optimization of tasks arrangement,service provision and parts processing has a large number of applications in the field of manage-ment decision making,which can produce huge social and economic benefits.In the classical scheduling theory,it is assumed that the job parameters are fixed constants and performance of the machine will not change during the whole scheduling horizon.However,the complex production process and customers' diversified demand faced by management decision maker make the object of study in scheduling field change correspondingly.The time parameters of the jobs can be changed,and the machine may also need to be interrupted for a period of time for maintenance,tool change,rate-modifying and other activities.At the same time,the pa-rameters of the jobs/machine are always controllable.In view of this new change,this paper mainly studies the production scheduling problem with controllable time parameters and the corresponding optimization algorithm.Firstly,single machine scheduling problems with resource-dependent release times is stud-ied.Each job starts as soon as it is released and release cost will be generated if its actual release time deviates from the supposed initial release time.The objective is determining a sequence of jobs in addition to their release times concurrently,in order that weighted release cost,makespan and total completion times of jobs are minimized.Two cases are considered,in which the prob-lem with restricted initial release time is NP-hard and the problem with unrestricted initial release time is polynomially solvable in O(nlong n)time by efficient algorithm with the analy-sis of optimality properties.Secondly,single machine scheduling problems with resource-and position-dependent job precessing times is studied,since such scheduling problems involving controllable but variable processing times can be found in many real-life applications.Based on the compressed process-ing times resulting from resource allocation,general position-dependent learning/aging effects are integrated in the actual processing times.The resource consumption function is either linear or convex and in each case two objective functions are considered.One is to minimize a cost function containing makespan,flow time,total absolute differences in completion times and total compression cost,another is to minimize a cost function containing earliness,tardiness,due-date and total compression cost.We present that each problem can be optimally solved in O(n3)time.We also present that a special case of the problem in convex model can be solved in O(n log n)time.Thirdly,scheduling problems with either resource allocation or machine availability con-straint is important and has received much attention recently.The coordination between job controllability and machine availability is considered when these two phenomena exist simulta-neously.It is assumed that convex resource-dependent jobs are scheduled on a single machine with an given unavailable time-window.Two objectives,namely the makespan and the total resource consumption,are concerned.The goal is to find an optimal job schedule and resource allocation for each job such that one objective is minimized under the constraint that another ob-jective does not exceed a given upper bound.It is shown that each problem under consideration is NP-hard.Heuristics are developed and their worst-case performance ratios are analyzed.Next,the makespan problem on identical parallel machines with special linearly compress-ible processing times is studied.The processing time of a job is compressible by using additional resource and the total compression amount is limited.It is assumed that each job processing time is reducible even to zero with enough resource consumption.Complexity and a MIP model for the considered problem are presented.Based on the analysis of simple scheduling rules about the classic makespan problem on parallel machines,two heuristics,namely LS-Compression and LNPT-Compression,are proposed.Moreover,the worst-case error-bounds are shown to evaluate the performances of the two heuristics.Then,scheduling problems with convex resource-dependent processing times involving position-dependent workloads are studied.More and more attention is paid to the scheduling problems with resource allocation,since it is in line with many real situations of production.Two machine settings,namely parallel machines and single machine,and two objective func-tions,namely the total scheduling cost and resource consumption cost,are concerned.Eight variants of problem are discussed,which differ in either the machine setting,the resource con-sumption function,or the objective function.It is shown that the optimal solution of each prob-lem under consideration can be obtained by polynomial time algorithm.And then,scheduling problems with a deteriorating and resource-dependent maintenance activity on a single-machine is investigated.The duration of the maintenance is assumed to be dependent both on its starting time and on the resource allocated to it.The objective is determin-ing the job sequence,the position to perform a maintenance activity and the amount of additional resource allocated to it such that the total cost of related measure and resource is minimized.The measures considered are the makespan,flow time,maximum tardiness and combination of earliness,tardiness and due-date.Analysis results show that all the considered problems are polynomially solvable,and the corresponding optimization algorithms are provided.Finally,common due-window assignment and scheduling problems with general position-dependent processing times involving deteriorating and compressible maintenance activity on a single-machine are considered.Two models associated with rate-modifying maintenance activ-ity are examined,in which the duration of maintenance is assumed to be either time-dependent and compressible or position-dependent and compressible.The objective is to find jointly the location and size of due-window,position of maintenance as well as resource amount allocated to it and job sequence to minimize a total cost function based on earliness,tardiness,window location,window size and resource cost.It is shown that the problem considered in each of the two models' setting can be optimally solved with polynomial time algorithm by reducing to assignment problem.In conclusion,the change of the job feature/machine environment makes the job/machine parameters not only variable but controllable.The corresponding study of production schedul-ing models and optimization algorithms which adapts to it further enrich the scheduling theory of decision making and extend its application areas.