Parallel-machine Scheduling With Potential Disruption And Positional-dependent Processing

The scheduling problem is a significant branch in operations research and cybernetics,and numerous papers involving it are published.Among these classic scheduling problems,it is supposed that the completion time of a job is constant,as well as the machine can continuously process job during this process.The actual scheduling problems possess complex properties,it is well known that the processing time of a job varies with the different start time.When the job processing start time is prolonged too much,the actual total completion time may be amounted,along with it the worse work efficiency will come,and sometimes it presents opposite results.It is also can be seen that sometimes the actual completion of job is independent on position.At the same time,due to the inner and external conditions,the machines will stop work when processing job.Based on these,in this paper we perform an investigation for the parallel-machine scheduling with potential disruption and positional-dependent processing in which the actual completion time is a general function independent on position.When we power machines,some random events may occur and lead them to stop work.Thus,here it is supposed that the start time of events breaking out is known in advance,and they will continue to effect at a certain possibility in a long time.On the conditions that some random events occur.we consider two cases,namely resumable case and non-resumable case,to minimize the expected total completion time,and perform an analysis and formulation of pseudo-polynomial time algorithm for the complexity of different cases.What the paper says is organized as follows:The non-resumable case.In the case that the amount of machine is fixed,the corresponding problem is shown an NP-hard problem and a dynamic pseudo-polynomial time algorithm is formulated,which further means the corresponding problem is an NP-hard problem.Here we only consider two-machines case in which a machine can breaks down,following this,we point out that how to generalize the corresponding conclusions to m-machines where K machines may break down.The resumable case.When we change the amount of machines,we prove that the corresponding problems becomes a strong NP problem;Similarly,in the case that the amount of machines is fixed and at last two machines break down,we show that the corresponding problem is NP hard,and design a dynamic pseudo-polynomial time algorithm,all this shows that the corresponding problem is a general NP hard problem.However,it is also unknown whether the case where only a machine is broken down means a NP hard.