Research On Mathematic Modeling And Meta-Heuristics For Solving Assembly Line Balancing Problem With Sequence-Dedpendent Setup Time

Since the assembly line was successfully applied to automobile factory by Ford,assembly line has been widely used in the production of daily necessities,food and electronic consumer goods.Owing to the high cost of assembly lines,how to design an efficient and low-cost assembly line is one of the effective measures for manufacturing enterprises in the fierce competition.As a key problem of assembly line design problem,the assembly line balancing problem has been proved to be a NP hard problem,which has been concerned by academia since 1950 s.It is worth mentioning that a large number of scholars focus too much on solving the simplest assembly line balancing problem,but ignore the complex constraints in the actual assembly process.This paper focuses on the influence of sequence-dependent setup time on assembly line balance,and this type of problem can be called as sequence-dependent problem.Because of its advantages of shorter line length,less work in process and less material handling cost,two-sided/ multi-manned assembly line is widely used in the production of large and complex products such as automobiles,motorcycles and heavy machinery equipment.Although the two-sided assembly line balancing problem has been studied by a great deal of researchers in the literature,the research on the multi-manned assembly line balancing problem is relatively limited.Moreover,there are very few literatures considering the setup time in the two-sided / multi-manned assembly line balancing problem,and there are many deficiencies.The main research work and results are as follows:(1)In order to solve the two-sided assembly line balancing problem with sequence dependent setup time,the model proposed in the previous literature is modified,the effectiveness of the heuristic algorithm based on various priority rules is verified,and an improved variable neighborhood search algorithm is designed.In order to improve the algorithm,a Petri net based coding method of feasible job sequence is designed;the side assignment rules are established to reduce the sequence-dependent idle time;An auxiliary objection is added to reduce the idle time of the earlier opened station;four kinds of neighborhood structures,which searching space is increasing one by one,are designed to enhance the search ability of the algorithm.The model and algorithm are used to solve benchmark examples to verify their effectiveness.(2)Aiming at the sovling the mixed-model two-sided assembly line balancing problem with sequence-dependent setup time,a new mathematical model is established to distinguish the forward sequence-dependent setup time and backward sequence-dependent setup time.The method of calculating the lower bound of the problem is given,and the improved variable neighborhood search algorithm proposed in Chapter 1 is modified.In the algorithm modification,a priority based matrix is used to determine the assignment task set in decoding,and the relationship between the setup time and idle time between different models should be considered to determine the finishing time of the task;when all task have been assigne,the last mated-workstationshould be adjusted to further reduce the number of opened stations.The proposed model and algorithm are used to solve benchmark examples to verify their effectiveness.(3)Aiming at the balancing the problem of multi-manned assembly line with sequence dependent setup time,a new mathematical model is established on the basis of distinguishing forward sequence-dependent setup time and backward sequence-dependent setup time,an algorithm for calculating the lower bound of the problem is given,and an improved simulated annealing search algorithm is proposed.A task priority-based coding method is designed;A allocation rule for reducing the idle time in the station are designed in decoding process,and more workers should be assigned to the earlier opened station as far as possible;while considering the idle time and setup time,the worker who can start the task earlier is selected to reduce the sequence-dependent idle time;The algorithm parameters are optimized by Taguchi experiment method;The proposed model and algorithm are used to solve benchmark examples and examples to verify their effectiveness.(4)Owing to the incapability of the traditional approaches in solving the mixed-model multi-manned assembly line balancing problem,a new mixed integer mathematical model was built by introducing new variants and unequal constraints.What's more,a modified chicken swarm optimization was also proposed.The algorithm adopts a task priority-based coding and in decoding procedure,a worker which the assigned task can start earlier is being selected to reduce the sequence-dependent idle time,and the number of workers is decided by the designed station assignment rules to rude the mean station idle time.Moreover,in order to achieve more systematic and efficient search,the chicken swarm is divided into three groups according to the fitness values of the chickens themselves.The proposed model and algorithm are used to solve benchmark examples and examples to verify their effectiveness.