We focus on the weapon target assignment and fire scheduling problem (WTAFSP) with the objective of minimizing the makespan, i.e., the latest completion time of a given set of firing operations. In this study, we assume that there are m available weapons to fire at n targets (> m). The artillery attack operation consists of two steps of sequential procedure : assignment of weapons to the targets; and scheduling firing operations against the targets that are assigned to each weapon. This problem is a combination of weapon target assignment problem (WTAP) and fire scheduling problem (FSP). To solve this problem, we define the problem with a mixed integer programming model. Then, we develop exact algorithms based on a dynamic programming technique. Also, we suggest how to find lower bounds and upper bounds to a given problem. To evaluate the performance of developed exact algorithms, computational experiments are performed on randomly generated problems. From the results, we can see suggested exact algorithm solves problems of a medium size within a reasonable amount of computation time. Also, the results show that the computation time required for suggested exact algorithm can be seen to increase rapidly as the problem size grows. We report the result with analysis and give directions for future research for this study. This study is meaningful in that it suggests an exact algorithm for a more realistic problem than existing researches. Also, this study can provide a basis for developing algorithms that can solve larger size problems.

본 연구는 통합공정일정계획(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을 이용하여 성능을 평가한다.

In the painting process of automotive factory, color changeover cost is incurred every time the color of vehicle is changed. To solve this problem, automotive company usually uses storage space such as Selectivity Banks(SB) or Car Rescheduling Storage and carries out sequence planning so that vehicles of the same color are consecutive, which is called Car Resequencing Problem (CRP). So far, research works for CRP has focused on algorithms finding optimal or approximated optimal solutions under the condition that the number of vehicles is fixed in SB. However, these results cannot be directly applied to the actual automotive paint shops since they have continuous flows of cars into SB to be handled in a day. Therefore, in this paper, we propose an efficient cyclic scheduling method that starts the painting process using the result of Accelerated Dynamic Programming (ADP) and then reapplies the ADP to the vehicles in SB for renewing the painting schedule whenever a certain number of vehicles is painted, represented as a threshold. To show the effectiveness of the proposed method, we performed a numerical experiment by designing system configurations, based onthe actual vehicle painting process, and proposed a good threshold that can reduce overall color changeover cost.

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.

We consider a satellite mission scheduling problem, which is a promising problem in recent satellite industry. This problem has various considerations such as customer importance, due date, limited capacity of energy and memory, distance of the location of each mission, etc. Also we consider the objective of each satellite such as general purpose satellite, strategic mission and commercial satellite. And this problem can be modelled as a general knapsack problem, which is famous NP-hard problem, if the objective is defined as to maximize the total mission score performed. To solve this kind of problem, heuristic algorithm such as taboo and genetic algorithm are applied and their performance are acceptable in some extent. To propose more efficient algorithm than previous research, we applied a particle swarm optimization algorithm, which is the most promising method in optimization problem recently in this research. Owing to limitation of current study in obtaining real information and several assumptions, we generated 200 satellite missions with required information for each mission. Based on generated information, we compared the results by our approach algorithm with those of CPLEX. This comparison shows that our proposed approach give us almost accurate results as just less than 3% error rate, and computation time is just a little to be applied to real problem. Also this algorithm has enough scalability by innate characteristic of PSO. We also applied it to mission scheduling problem of various class of satellite. The results are quite reasonable enough to conclude that our proposed algorithm may work in satellite mission scheduling problem.

We focus on the fire scheduling problem (FSP), the problem of determining the sequence of targets to be fired at, for the objective of minimizing makespan to achieve tactical goals. In this paper, we assume that there are m available weapons to fire at n targets (> m) and the weapons are already allocated to targets. One weapon or multiple weapons can fire at one target and these fire operations should start simultaneously while the finish time of them may be different. We develop several dominance properties and a lower bound for the problem, and suggest a branch and bound algorithm implementing them. Also, In addition, heuristic algorithms that can be used for obtaining an initial upper bound in the B&B algorithm and for obtaining good solutions in a short time were developed. Computational experiments are performed on randomly generated test problems and results show that the suggested algorithm solves problems of a medium size in a reasonable amount of computation time. The proposed lower bound, the dominance properties, and the heuristics for upper bound are tested in B&B respectively, and the result showed that lower bound is effective to fathoming nodes and the dominance properties and heuristics also worked well. Also, it is showed that the CPU time required by this algorithm increases rapidly as the problem size increases. Therefore, the suggested B&B algorithm would be limited to solve large size problems. However, the employed heuristic algorithms can be effectively used in the B&B algorithm and can give good solutions for large problems within a few seconds.

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.

본 논문은 조립과 분리시스템이 혼합된 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%.

본 연구는 반도체 제조공정에서 사용되는 단일 Burn-In oven에서의 Total weighted earliness와 Tardiness를 최소화하기 위한 생산 스케줄링을 결정하는 문제를 다룬다. 본 연구에서는 모든 작업은 상시에 시작가능하고 각각은 서로 다른 가중치를 가지고 있다고 가정하였다. 일반적으로 단일 Burn-In oven은 다양한 작업들이 동시에 가능한 Batch processing 기계이다. 따라서 다양한 작업들로 구성된 하나의 Batch

  This paper considers an integrated decision for scheduling and outsourcing(or, subcontracting) of a finite number of jobs(or, orders) in a time-sensitive make-to-order manufacturing environment. The jobs can be either processed in a parallel in-house fa

  This paper improves algorithms for an assembly-type flowshop scheduling problem in which each job is to assemble two types of components and makespan is the objective measure. For the assembly, one type of the components is outsourced with job-dependent

  This paper considers an assembly-type flowshop scheduling problem in which each job is assembled with two types of components. One type of the components is outsourced with positive lead time but the other type is fabricated in-house at the first stage.

This paper concerns on a multiprocessor task scheduling problem with precedence relation, in which each task requires several processors simultaneously Meta-heuristic generally finds a good solution If It starts from a good solution In this paper, a tabu

This paper considers a scheduling problem concerned with an assembly system where two components are first treated in their own parallel machines and then pulled to be assembled into a final product at a single assembly machine. The objective measure is t

In this paper a modified simulated annealing approach for solving single-machine mean tardiness scheduling problems is proposed. The results of the simulation indicate that the proposed method provides more stable solutions than those of previous studies. The proposed method also provides better quality solutions for large-size problems.

This paper concerns on a multiprocessor task scheduling problem with precedence relation, in which each task requires several processors at a time. The problem is to find a schedule of minimal time to complete all tasks. In this paper, a tabu search is presented. Numerical results show that tabu search yields a better performance than the previous studies.

This paper deals with the problem of batching and scheduling of jobs whose processing times are different respectively. But, they are given as not the exact value but the range from the lower limits to the upper, which makes it possible to group jobs into

This paper deals with the problem of batching and scheduling of jobs whose processing times are given as the duration from the lower limits to the upper, which makes it possible to group jobs into batches. The grouping of jobs is desirable because of the capability of the batch processor to accommodate several jobs at once. The time required to process the jobs in any batch depends on their lower limit processing times. Once processing is initiated on a batch processor, the batch cannot be interrupted, nor can other jobs be started. And all jobs are assumed to be simultaneously available. This paper develops the model to describe these situation and a heuristic method to minimize its total tardiness.

Column subtraction, originally proposed by Harche and Thompson(1994), is an exact method for solving large set covering, packing and partitioning problems. Since the constraint set of ship scheduling problem(SSP) have a special structure, most instances of SSP can be solved by LP relaxation This paper aim, at applying the column subtraction method to solve SSP which am not be solved by LP relaxation For remained instances of unsolvable ones, we subtract columns from the finale simplex table to get another integer solution in an iterative manner. Computational results having up to 10,000 0-1 variables show better performance of the column subtraction method solving the remained instances of SSP than complex branch and-bound algorithm by LINDO.