A widespread supposition on mixed-model assembly line-balancing problems assigns a task, which is shared between two or more models to a single station. Bukchin and Rabinowitch (European Journal of Operational Researc...
详细信息
A widespread supposition on mixed-model assembly line-balancing problems assigns a task, which is shared between two or more models to a single station. Bukchin and Rabinowitch (European Journal of Operational Research, 174:492-508, 2006) relaxed the restriction for mixed-model straight-line assembly line problems and allowed tasks common to multiple models to be assigned to different stations, called task duplication. In this paper, considering the same relaxation but for mixed-model U-shaped assembly lines, a novel geneticalgorithm (GA) approach for solving large-scale problems is developed. Although superiorities of U-shaped assembly lines over straight lines have been discussed in several articles, this paper makes the advantage more tangible by providing a quantitative example. This paper also presents a novel two-stage genetic algorithm which is fittingly devised for solving the new proposed model. In order to evaluate the effectiveness of the GA, one small-scale and one medium-scale problem are solved using both the proposed GA and Lingo 8.0 software, and the obtained outcomes are compared. The computational results indicate that the GA is capable of providing high-quality solutions for small- and medium-scale problems in negligible central processing unit (CPU) times. It is worth mentioning that, for large-scale problems, such as Kim and Arcus test problems, no analogous results for those obtained by our proposed GA exist. To conclude, it can be said that the proposed GA performs well and is able to solve large-scale problems within acceptable CPU times.
In a flexible job-shop scheduling problem (FJSP), an operation can be assigned to one of a set of eligible machines. Therefore, the problem is to simultaneously determine both the assignment of operations to machines ...
详细信息
In a flexible job-shop scheduling problem (FJSP), an operation can be assigned to one of a set of eligible machines. Therefore, the problem is to simultaneously determine both the assignment of operations to machines and their sequences. Accordingly, the solution encoding of many regular geneticalgorithms (RGAs) developed in literature has two parts: one part encodes the assignment decision and the other the sequencing decision. The genetic search determines both the assignment and the sequencing of the operations simultaneously through a random process guided by the principles of natural selection and evolution. In this paper, we develop a two-stage genetic algorithm (2SGA) with the first stage being different from a typical RGA for FJSP found in the literature. The first stage of 2SGA has a solution encoding that only dictates the sequence in which the operations are considered for assignment. Whenever an operation is considered for assignment, the machine that can complete this operation the soonest is selected while taking into account the operations that are already assigned to this machine. The order in which the operations are assigned to machines determines their sequence. The second stage, starting from the solutions of the first stage, follows the common approach of geneticalgorithm for FJSP to enable the algorithm to search the entire solution space by including solutions that might have been excluded because of the greedy nature of the first stage. We tested the proposed algorithm by solving many benchmark problems and several other large-size problems of a comprehensive FJSP model with sequence-dependent setup, machine release date, and lag-time. The performance of the proposed two-stagealgorithm greatly exceeds that of the common approach of geneticalgorithm for FJSP. We also show that further performance improvement of the proposed algorithm can be achieved using high-performance parallel computation. However, the more interesting result we found
Inspired by industrial issues and demands, we define a novel version of the Flexible Job Shop Scheduling Problem with Working Center. A working center is a group of machines performing the same type of operation. The ...
详细信息
ISBN:
(纸本)9789897585357
Inspired by industrial issues and demands, we define a novel version of the Flexible Job Shop Scheduling Problem with Working Center. A working center is a group of machines performing the same type of operation. The job operations of different types follow a strict sequence across the working centers, while any order is allowed among operations of the same type. This paper illustrates a geneticalgorithm with a two-stage chromosome representation, adapted genetic operators, local search, and social disaster technique to deal with a real-world industrial application. The algorithm has been tested on a classical benchmark to assess its adaptability and compare its performance with state-of-the-art techniques;then, we tested different variations of the proposed algorithm on a real-case test instance showing a consistent improvement when compared with the heuristic in use at the industrial company.
The work in this paper is motivated by a recently published article in which the authors developed an efficient two-stage genetic algorithm for a comprehensive model of a flexible job-shop scheduling problem (FJSP). I...
详细信息
The work in this paper is motivated by a recently published article in which the authors developed an efficient two-stage genetic algorithm for a comprehensive model of a flexible job-shop scheduling problem (FJSP). In this paper, we extend the application of the algorithm to solve a lot streaming problem in FJSP while at the same time expanding the model to incorporate multiple objectives. The objective function terms included in our current work are the minimization of the (1) makespan, (2) maximum sublot flowtime, (3) total sublot flow time, (4) maximum job flowtime, (5) total job flow time, (6) maximum sublot finish-time separation, (7) total sublot finish-time separation, (8) maximum machine load, (9) total machine load, and (10) maximum machine load difference. Numerical examples are presented to illustrate the greater need for multi-objective optimization in larger problems, the interaction of the various objective function terms, and their relevance in providing better solution quality. The ability of the two-stage genetic algorithm to jointly optimize all the objective function terms is also investigated. The results show that the algorithm can generate initial solutions that are highly improved in all of the objective function terms. It also outperforms the regular geneticalgorithm in convergence speed and final solution quality in solving the multi-objective FJSP lot streaming. We also demonstrate that high-performance parallel computation can further improve the performance of the two-stage genetic algorithm. Nevertheless, the sequential two-stage genetic algorithm with a single CPU outperforms the parallel regular geneticalgorithm that uses many CPUs, asserting the superiority of the two-stage genetic algorithm in solving the proposed multi-objective FJSP lot streaming.
In this paper, we study the problems a repair shop has with rescheduling after major supply disruptions. The repair shop provides repair and maintenance services to its customers. After a major disruption to productio...
详细信息
In this paper, we study the problems a repair shop has with rescheduling after major supply disruptions. The repair shop provides repair and maintenance services to its customers. After a major disruption to production, the repair shop faces delays in production and order delivery due to shortages in materials and/or labor, which requires rescheduling of all the unfinished parts. We observe that the finished parts incur high holding costs until the entire order is completed, while any unfinished parts (in the form of raw material or work-in-progress) incur low holding costs until production starts. Moreover, the repair shop incurs a setup cost when switching between different types of parts. Considering these new features, we formulate the rescheduling problem for the repair shop under a coordinated supply chain as an integer program to minimize the total tardiness, setup cost, and holding cost. To solve the model, we propose an innovative two-stage genetic algorithm, which utilizes the estimation of distribution algorithm (EDA) to improve the search process of the optimal solution. We test the performance of this algorithm on a dataset generated from the order data of a heavy machinery maintenance provider. The numerical results show that our model generates solutions that outperform the initial schedule, which was obtained by minimizing holding and setup costs without disruption. In addition, using other closely-related geneticalgorithms as benchmarks, we show that our algorithm outperforms the benchmarks without sacrificing the computational time. We also discuss an extension of the main model by considering the recovery of productivity in terms of processing time.
暂无评论