Research On Methods For Lot-streaming Flow Shop Scheduling Problems

Lot-streaming is an effective technique to implement optimal production technology, which can lead to reduction in production lead times and reduction in work-in-process inventory and associated costs, and accelerate the production process of jobs. The lot-streaming flowshop problem is an extension of the traditional flowshop problem. It is much more complex than the traditional one and is NP-hard as well. Due to the importance of the problem both in theory and in practice, it is attracted much more attention in recent years. This dissertation utilizes the recently presented Invasive Weed Optimization (IWO) and Artificial bee colony optimization (ABC) to solve several typical lot-streaming problems. These are the equal-size sublots lot-streaming flowshop scheduling problem (ELFSP), the ELFSP under no-idle case, the ELFSP under no-wait case, and the ELFSP with sequence-dependent setup times, and the integrated ELFSP. A number of effective and efficient scheduling methods have been presented based on the IWO, ABC, and some problem-specific characteristics.For the ELFSP, a mathematic model is first set up, and then an IWO-and an ABC-based algorithm are respectively presented to minimize makespan and total flowtime. In the two algorithms, the individuals are represented as the permutations of batches, and some operators specially designed for the permutations are employed to generated new solutions. The two algorithms directly perform search process in the discrete domain and are so called discrete IWO (DIWO) and discrete ABC (DABC), separately. Further, a heuristic-based initialization is adopted to generate an initial population with a high level of diversity and quality. A speedup technology is proposed for evaluating the whole insertion neighborhoods with regarding to the similarity of neighborhood solutions. Some improvements are implemented for generating new solutions, selection operators, and evolutionary mechanism. A local search procedure is imbedded to balance the algorithm’s exploration and exploitation. The algorithms are calibrated by the ANOVA and the trial and error method. Comparative evaluations are carried out with the best performing nine algorithms from the literature. The results show that the proposed DIWO and DABC algorithms are new state-of-the-art algorithms for solving the ELFSP with the makespan and total flowtime criterion, respectively.For the ELFSP under no-idle cases (here we consider no machine idle time between two successive sublots only in the same batch and in both the same and different batches), the ELFSP under no-wait case, and the ELFSP with sequence-dependent setup times, different mathematic models are proposed. The above DIWO and DABC are used to minimize makespan and total flowtime for these problems, respectively. Some operators are redesigned considering different characteristics of different problems. These are the calculations of makespan and total flowtime, decoding methods and speedup technologies which are very closely related to the specific problems. We compare our algorithms with those from literature by extensive numerical experiments. The comparative results demonstrate the superiority and effectiveness of the DIWO and DABC for the problems under consideration.In the integrated ELFSP, both lot-splitting and batch sequencing are simultaneously addressed. A mathematical model is first presented to describe the problem. And then, following their successful application in the above problems, the DIWO and DABC are also employed here. The DIWO is used to solve the problem with makespan criterion.In the DIWO, a novel representation is presented which divided an individual into two parts, one for batch splitting and other for batch sequencing.±1mutation and random mutation are proposed for the batch splitting, whereas insertion and swap operators are employed for batch sequencing. Six kinds of neighborhood operators are investigated. And a local search is used to enhance DIWO’s local exploitation. The DABC is used to solve the problem with total flowtime criterion. In the DABC, a new parameter is introduced to control the search behavior of employees and onlookers so as to balance the algorithm’s exploitation and exploration, and the scout phase is improved to lead the algorithm to most promising region. The effectiveness of the presented DIWO and DABC for the integrated ELFSP is demonstrated by extensive experimental comparison.Based on the above study for different ELFSPs, some examples from real-world production process are also considered. We use our algorithms to schedule the production data from the flowshop of producing engine connecting rods. The results show that the proposed algorithms are feasible and effective for the real-world lot-streaming flowshop scheduling problems.Finally, we summarize our dissertation and point out some research topics about the lot-streaming scheduling problems in the future study.