Research On Scheduling Methods For Flexible Job-shops With Lot-streaming And Machine Reconfigurations

To expeditiously satisfy diversified and personalized market demands,the primary production mode of manufacturing systems is gradually shifting to the multi-variety and batch production.Flexible job shop,in which a large amount of identical jobs can be split into several sublots and be processed by reconfigurable machines with multiple technics,has become a main focus for the aforementioned production mode.However,such highly flexible environments bring extra decision-making processes for reconfiguring machines and dividing jobs into sublots,where previous schedules are frequently interrupted by dynamic events.The complexity of decision-making problems and uncertainty in the environment make the production scheduling extremely challenging.Matheurisitic is a methodology that combines the advantages of meta-heuristics and mathematical programming approaches,and has been regarded as a promising solution for intractable scheduling problems.This dissertatin formulates static scheduling and rescheduling models for typical multi-variety and batch production scenarios,and proposes efficient scheduling methods based on matheuristics.The proposed algorithms have been validated on both benchmark sets and real-world industrial cases.The research work of this dissertation is presented as follows:To address flexible job-shop scheduling problems with machine reconfigurations（FJSP-MR）,a mixed integer linear programming（MILP）model is formulated for the total weighted tardiness minimization.An improved genetic algorithm（IGA）is proposed with problem-specific encoding and decoding strategies.During the local search phase of the IGA,a disjunctive graph model with multiple arcs is established to describe setup activities for machine reconfigurations.Afterwards,decision conditions of the classical k-insertion are simplified according to characteristics of the proposed disjunctive graph model.The MILP model and IGA are validated on randomly-generated test instances.To address the flexible job-shop scheduling problems with lot-streaming and machine reconfigurations（FJSP-LSMR）,an MILP model is formulated for the total weighted tardiness minimization,and a matheuristic with variable neighborhood search（MH-VNS）is proposed.With regard to the two decision-making processes of a lot-sizing sub-problem,two MILP models with different lot-sizing flexibility are established to improve lot-sizing plans of given incumbent solutions.Experimental results suggest that proposed MILP models for the lot-sizing sub-problem can obtain optimal lot-sizing plans in a short time,and help the MH-VNS to continuously improve solutions during the later period.In consideration of the production stability under dynamic events,such as machine breakdowns and job insertions,an MH-VNS is proposed to address the flexible job-shop rescheduling problem with lot-streaming and machine reconfigurations（FJRP-LSMR）.For the local search function,an MILP model is re-formulated with dynamic event-related constraints,where the total deviation of completion time is also included.The proposed MH-VNS is tested on randomly-generated instances to demonstrate the advantages in both optimality and stability.In the situation that previous sublots are allowed to be re-organized,an MH-VNS considering re-lot-sizing(MH_RLS-VNS)is proposed to address the FJRP-LSMR with re-lot-sizing(FJRP_RLS-LSMR).After analyzing the characterisitic of rescheduling processes in flexible job shops,two re-lot-sizing strategies,namely complete re-lot-sizing and partial re-lot-sizing,are defined to include more sublots for the rescheduling,thus the solution space that can be visited by the MILP model is greatly expanded.The proposed MH_RLS-VNS is tested on randomly-generated instances for the validation.Take a domestic shop floor for processing large-sized structural parts as an example,a flexible job-shop scheduling problem with lot-streaming and machine reconfigurations is abstracted from this scenario.A scheduling software with aforementioned matheuristic-based scheduling methods is developed,and is adopted to address real-world cases from the enterprise.The developed software gives high-quality long-term scheduling plans and shor-term rescheduling plans efficiently,which implies the proposed matheuristic algorithms are effective in large-scale scheduling problems in industries.Finally,the main contributions and novelty of this dissertation are summarized,and some possible research directions are discussed.