The Study Of Hybrid Job-shop Scheduling With Multiprocessor

Shop scheduling plays an important role in the management of manufacturing companies,which has functions of efficiency improvement,cost reduction and competitiveness enhancement.In the field of scheduling,one of the most classic model is the Job-shop Scheduling Problem(JSP),a simplified model for many shop production system,which is used widely in the manufacturing industry.However,the situation that some operations need to be processed simultaneously on more than one processors(workers,equipments or other resources)makes it a challenge for JSP which assumes that all the operations have to be processed by only one processor.This paper calls the new problem as Hybrid Job-shop Scheduling with Multiprocessor Tasks(HJSMT)with widely usage in the real production system,the study on which has a great theoretic and applicable significance.Goals of this paper is giving an investigation on HJSMT,establishing mathematical formulation and proposing a good algorithm.In details,the research begins with an simplified HJSMT model where each job has only one operation and extends to the general model where there are more than one operations in a job.For solving the problem,a Particle Swarm Optimization(PSO)algorithm is developed which is improved in paricles encoding schemes,ways of information exchanging,fitness function establishment and local search enhancement.Finally,experimental results shows that the proposed algorithm has a good performance in benchmark problems of both HJSMT and JSP where the famous JSP instances "FT10" and "FT20" are solved optimally.In the real production system,there exist many uncertain factors which has a great difference on the schedule implementation,making it necessary to go on a research on stochastic HJSMT model with the basis of the determined one.Considering the scheduling robustness,a mathemathic stochastic model is constructed with scenarios and a robust optimization model,the Expected Cmax and the Worst scenario Model(ECWM)is proposed for solving it.In the experiment section,the ECWM is applied to the stochastic HJSMT instances and gets good results,indicating that the schedule produced by ECWM has a good expected makespan as well as robustness.