This paper proposes an algorithm for the Unrelated Parallel Machine Scheduling Problem(UPMSP) without setup times, aiming to minimize total tardiness. As an NP-hard problem, the UPMSP is hard to get an optimal solution. Consequently, practical scenarios are solved by relying on operator's experiences or simple heuristic approaches. The proposed algorithm has adapted two methods: a policy network method, based on Transformer to compute the correlation between individual jobs and machines, and another method to train the network with a reinforcement learning algorithm based on the REINFORCE with Baseline algorithm. The proposed algorithm was evaluated on randomly generated problems and the results were compared with those obtained using CPLEX, as well as three scheduling algorithms. This paper confirms that the proposed algorithm outperforms the comparison algorithms, as evidenced by the test results.

This paper is proposing a novel machine scheduling model for the unrelated parallel machine scheduling problem without setup times to minimize the total completion time, also known as “makespan”. This problem is a NP-complete problem, and to date, most approaches for real-life situations are based on the operator’s experience or simple heuristics. The new model based on the Memetic Algorithm, which was proposed by P. Moscato in 1989, is a hybrid algorithm that includes genetic algorithm and local search optimization. The new model is tested on randomly generated datasets, and is compared to optimal solution, and four scheduling models; three rule-based heuristic algorithms, and a genetic algorithm based scheduling model from literature; the test results show that the new model performed better than scheduling models from literature.

본 연구는 통합공정일정계획(Integrated Process Planning and Scheduling; IPPS)의 최적화를 위한 계산 효율성이 높은 탐욕적 휴리스틱과 유전알고리즘(Genetic Algorithm; GA)을 결합한 하이브리드형 유전 알고리즘을 제안한다. IPPS는 기존의 공정계획과 일정계획을 동시에 풀고자 하는 NP-Hard 문제이다. 특히, 본 연구에서 다루는 IPPS는 tool related constraints가 포함된 것으로서 전통적인 GA는 수행도중 infeasible schedule을 빈번히 발생시킨다. 제안하는 방법의 아이디어는 전체적인 schedule의 구조에 영향을 미치는 operation의 sequence와 machine의 결정은 GA의 procedure를 따르고, 목적함수의 부분계산이 가능한 tool과 Tool Access Direction(TAD)는 greedy heuristics을 통하여 infeasibility를 해소하자는 것이다. 이를 통하여 계산시간의 급격한 증가 없이 또는 기존에 비해 계산시간을 감소시키면서 좋은 품질의 해를 구할 수 있다. 본 연구에서 제안하는 알고리즘은 benchmark problems을 이용하여 성능을 평가한다.

This research focuses on a scheduling problem in the semiconductor probing facility. Probing facility is composed of identical parallel machines and the parallel machines form three workstations for the tests with different recipes. Each machine can be set to three different tests and sequence-dependent setup times are required between operations due to temperature and probe card loading/unloading. Precedence relationship exists between three tests of each wafer lot. The scheduling problem for the probing facility is a parallel machine scheduling problem with precedence relationship and sequence dependent setup time. We develop heuristic algorithm to minimize makespan for the scheduling problem and numerical experiments are conducted to evaluate the performance.

This paper proposes an improved standard genetic algorithm (GA) of making a near optimal schedule for integrated process planning and scheduling problem (IPPS) considering tool flexibility and tool related constraints. Process planning involves the selection of operations and the allocation of resources. Scheduling, meanwhile, determines the sequence order in which operations are executed on each machine. Due to the high degree of complexity, traditionally, a sequential approach has been preferred, which determines process planning firstly and then performs scheduling independently based on the results. The two sub-problems, however, are complicatedly interrelated to each other, so the IPPS tend to solve the two problems simultaneously. Although many studies for IPPS have been conducted in the past, tool flexibility and capacity constraints are rarely considered. Various meta-heuristics, especially GA, have been applied for IPPS, but the performance is yet satisfactory. To improve solution quality against computation time in GA, we adopted three methods. First, we used a random circular queue during generation of an initial population. It can provide sufficient diversity of individuals at the beginning of GA. Second, we adopted an inferior selection to choose the parents for the crossover and mutation operations. It helps to maintain exploitation capability throughout the evolution process. Third, we employed a modification of the hybrid scheduling algorithm to decode the chromosome of the individual into a schedule, which can generate an active and non-delay schedule. The experimental results show that our proposed algorithm is superior to the current best evolutionary algorithms at most benchmark problems.

The systematic management of technology infrastructure increasingly becomes critical as it represents the driving power for creating competitive advantage of nations and enterprises. In this sense, public facility and equipment, which is one major asset of technology infrastructure, should be managed effectively, systematically and efficiently to increase its overall equipment effectiveness. However, the manual and off-line communication was the unique way to communicate between the suppliers who provide facilities in the public sector and the customers who utilize the facilities in the industrial sector. This communication way caused invisibility of available usage time and increase of idle time, thereby decreasing the equipment effectiveness. This paper presents an web-based scheduling system that enables real-time collaboration and information sharing for increasing the equipment effectiveness. The designed system performs scheduling, facility management, order management and customer relationship management in an on-line platform, and carries out the processing and storing of relevant information in an integrated database. The paper includes a development approach to identify business process models and standardized system models by using object-modeling technique. The deliverable of the present work will contribute to increasing the equipment effectiveness by enhancing visibility, transparency and predictability by means of the integration with a legacy Enterprise Resource Planning.

This paper considers the allocation and engagement scheduling problem of interceptor missiles, and the problem was formulated by using MIP (mixed integer programming) in the previous research. The objective of the model is the maximization of total intercept altitude instead of the more conventional objective such as the minimization of surviving target value. The concept of the time window was used to model the engagement situation and a continuous time is assumed for flying times of the both missiles. The MIP formulation of the problem is very complex due to the complexity of the real problem itself. Hence, the finding of an efficient optimal solution procedure seems to be difficult. In this paper, an efficient genetic algorithm is developed by improving a general genetic algorithm. The improvement is achieved by carefully analyzing the structure of the formulation. Specifically, the new algorithm includes an enhanced repair process and a crossover operation which utilizes the idea of the PSO (particle swarm optimization). Then, the algorithm is throughly tested on 50 randomly generated engagement scenarios, and its performance is compared with that of a commercial package and a more general genetic algorithm, respectively. The results indicate that the new algorithm consistently performs better than a general genetic algorithm. Also, the new algorithm generates much better results than those by the commercial package on several test cases when the execution time of the commercial package is limited to 8,000 seconds, which is about two hours and 13 minutes. Moreover, it obtains a solution within 0.13 ~33.34 seconds depending on the size of scenarios.

This paper deals with rescheduling on unrelated parallel-machines with compressible processing times, assuming that the arrival of a set of new jobs triggers rescheduling. It formulates this rescheduling problem as an assignment problem with a side constraint and proposes a heuristic to solve it. Computational tests evaluate the efficacy of the heuristic.

Lot-streaming is the process of splitting a job (lot) into sublots to allow the overlapping of operations between successive machines in a multi-stage production system. A new genetic algorithm (NGA) is proposed for an n-job, m-machine, lot-streaming flow shop scheduling problem with equal-size sublots in which the objective is to minimize the total stretch. The stretch of a job is the ratio of the amount of time the job spent before its completion to its processing time. NGA replaces the selection and mating operators of genetic algorithms (GAs) by marriage and pregnancy operators and incorporates the idea of inter- chromosomal dominance and individuals’ similarities. Extensive computational experiments for medium to large-scale lot-streaming flow-shop scheduling problems have been conducted to compare the performance of NGA with that of GA.

This paper considers a scheduling problem in a two-machine flowshop with outsourcing strategy incorporated. The jobs can be either processed in the first machine or outsourced to outside subcontractors. This paper wants to determine which jobs to be processed in-house and which jobs to be outsourced. If any job is decided to be outsourced, then an additional outsourcing cost is charged The objective of this paper is to minimize the sum of scheduling cost and outsourcing cost under a budget constraint. At first this paper characterizes some solution properties, and then it derives solution procedure including DP (Dynamic Programming) and B&B (Branch-and-Bound) algorithms and a greedy-type heuristic. Finally the performance of the algorithms are evaluated with some numerical tests.

In this paper, we deal with a single machine scheduling problems integrating with step deterioration effect and a rate-modifying activity (RMA). The scheduling problem assumes that the machine may have a single RMA and each job has the processing time of a job with deterioration is a step function of the gap between recent RMA and starting time of the job and a deteriorating date that is individual to all jobs. Based on the two scheduling phenomena, we simultaneously determine the schedule of step deteriorating jobs and the position of the RMA to minimize the makespan. To solve the problem, we propose a hybrid typed genetic algorithm compared with conventional GAs.

We consider the capacitated lot-sizing and scheduling problem for a paper remanufacturing system that produces several types of corrugated cardboards. The problem is to determine the lot sizes as well as the sequence of lots for the objective of minimizin

This paper considers a 2-stage assembly flowshop scheduling problem where each job is completed by assembling multiple components. The problem has the objective measure of minimizing total completion time. The problem is shown to be NP-complete in the str

본 논문은 조립과 분리시스템이 혼합된 Fork-and-Join 시스템에서의 일정계획문제를 고려하고 있다. 최초 단계에서는 구성품 단위로 분리가 발생하고 두 번째 단계에서는 부품생산단계에서 각 부품 또는 구성품이 서로 다른 설비와 경로를 통해 독립적으로 생상된 후 최종 조립단계로 이동하게 되고, 그곳에서 조립공정을 통해 제품으로 안성된다. 본 논문에서는 이러한 Fork-and-Join 시스템에서 최종완료시간(makespan)을 최소화 할 수 있는 발견적

This paper considers a coordinated scheduling problem between multi-suppliers and an manufacture. When the supplier has insufficient inventory to meet the manufacture's order, the supplier may use the expedited production and the expedited transportation. In this case, we consider a scheduling problem to minimize the total cost of suppliers and manufacture. We suggest an population management genetic algorithm with local search and crossover (GALPC). By the computational experiments comparing with general genetic algorithm, the objective value of GALPC is reduced by 8% and the calculation time of GALPC is reduced by 70%.

  Ultra-high voltage transformer industry has characteristic of small quantity batch production system by other order processing unlike general mass production systems. In this industry, observance of time deadline is very important in market competitive