No Tardiness Rescheduling with Order Disruptions

Yang, Jaehwan Korean Institute of Industrial Engineers 2013 Industrial Engineeering & Management Systems Vol.12 No.1

This paper considers a single machine rescheduling problem whose original (efficiency related) objective is minimizing makespan. We assume that disruptions such as order cancelations and newly arrived orders occur after the initial scheduling, and we reschedule this disrupted schedule with the objective of minimizing a disruption related objective while preserving the original objective. The disruption related objective measures the impact of the disruptions as difference of completion times in the remaining (uncanceled) jobs before and after the disruptions. The artificial due dates for the remaining jobs are set to completion times in the original schedule while newly arrived jobs do not have due dates. Then, the objective of the rescheduling is minimizing the maximum earliness without tardiness. In order to preserve the optimality of the original objective, we assume that no-idle time and no tardiness are allowed while rescheduling. We first define this new problem and prove that the general version of the problem is unary NP-complete. Then, we develop three simple but intuitive heuristics. For each of the three heuristics, we find a tight bound on the measure called modified z-approximation ratio. The best theoretical bound is found to be 0.5 - ${\varepsilon}$ for some ${\varepsilon}$ > 0, and it implies that the solution value of the best heuristic is at most around a half of the worst possible solution value. Finally, we empirically evaluate the heuristics and demonstrate that the two best heuristics perform much better than the other one.

No Tardiness Rescheduling with Order Disruptions

양재환 대한산업공학회 2013 Industrial Engineeering & Management Systems Vol.12 No.1

This paper considers a single machine rescheduling problem whose original (efficiency related) objective is minimizing makespan. We assume that disruptions such as order cancelations and newly arrived orders occur after the initial scheduling, and we reschedule this disrupted schedule with the objective of minimizing a disruption related objective while preserving the original objective. The disruption related objective measures the impact of the disruptions as difference of completion times in the remaining (uncanceled) jobs before and after the disruptions. The artificial due dates for the remaining jobs are set to completion times in the original schedule while newly arrived jobs do not have due dates. Then, the objective of the rescheduling is minimizing the maximum earliness without tardiness. In order to preserve the optimality of the original objective, we assume that no-idle time and no tardiness are allowed while rescheduling. We first define this new problem and prove that the general version of the problem is unary NP-complete. Then, we develop three simple but intuitive heuristics. For each of the three heuristics, we find a tight bound on the measure called modified z-approximation ratio. The best theoretical bound is found to be 0.5 −ε for some ε > 0, and it implies that the solution value of the best heuristic is at most around a half of the worst possible solution value. Finally, we empirically evaluate the heuristics and demonstrate that the two best heuristics perform much better than the other one

No Tardiness Rescheduling with Order Disruptions

Jaehwan Yang 대한산업공학회 2013 Industrial Engineeering & Management Systems Vol.12 No.1

This paper considers a single machine rescheduling problem whose original (efficiency related) objective is minimizing makespan. We assume that disruptions such as order cancelations and newly arrived orders occur after the initial scheduling, and we reschedule this disrupted schedule with the objective of minimizing a disruption related objective while preserving the original objective. The disruption related objective measures the impact of the disruptions as difference of completion times in the remaining (uncanceled) jobs before and after the disruptions. The artificial due dates for the remaining jobs are set to completion times in the original schedule while newly arrived jobs do not have due dates. Then, the objective of the rescheduling is minimizing the maximum earliness without tardiness. In order to preserve the optimality of the original objective, we assume that no-idle time and no tardiness are allowed while rescheduling. We first define this new problem and prove that the general version of the problem is unary NP-complete. Then, we develop three simple but intuitive heuristics. For each of the three heuristics, we find a tight bound on the measure called modified z-approximation ratio. The best theoretical bound is found to be 0.5 ? ε for some ε > 0, and it implies that the solution value of the best heuristic is at most around a half of the worst possible solution value. Finally, we empirically evaluate the heuristics and demonstrate that the two best heuristics perform much better than the other one.

작업시간이 압축 가능한 경우 병렬기계의 재일정계획

Suhwan Kim 한국산업경영시스템학회 2015 한국산업경영시스템학회지 Vol.38 No.2

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.

작업시간이 압축 가능한 경우 병렬기계의 재일정계획

김수환 한국산업경영시스템학회 2015 한국산업경영시스템학회지 Vol.38 No.2

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.

An Approach to Optimal Dispatch Scheduling Incorporating Transmission Security Constraints

Koo-Hyung Chung,Dong-Joo Kang,Balho H. Kim,Tai-Hoon Kim,Tae-Kyoo Oh 대한전기학회 2008 Journal of Electrical Engineering & Technology Vol.3 No.2

The introduction of competition in electricity markets emphasizes the importance of sufficient transmission capacities to guarantee effective power transactions. Therefore, for the economic and stable electric power system operation, transmission security constrains should be incorporated into the dispatch scheduling problem. With the intent to solve this problem, we decompose a dispatch scheduling problem into a master problem (MP) and several subproblems (SPs) using Benders decomposition. The MP solves a general optimal power flow (OPF) problem while the SPs inspect the feasibility of OPF solution under respective transmission line contingencies. If a dispatch scheduling solution given by the MP violates transmission security constraints, then additional constraints corresponding to the violations are imposed to the MP. Through this iterative process between the MP and SPs, we derive an optimal dispatch schedule incorporating the post-contingency corrective rescheduling. In addition, we consider interruptible loads as active control variables since the interruptible loads can participate as generators in competitive electricity markets. Numerical examples demonstrate the efficiency of the proposed algorithm.

Generation Rescheduling Based on Energy Margin Sensitivity for Transient Stability Enhancement

Kyu-Ho Kim,Sang-Bong Rhee,Kab-Ju Hwang,Kyung-Bin Song,Kwang Y. Lee 대한전기학회 2016 Journal of Electrical Engineering & Technology Vol.11 No.1

This paper presents a generation rescheduling method for the enhancement of transient stability in power systems. The priority and the candidate generators for rescheduling are calculated by using the energy margin sensitivity. The generation rescheduling formulates the Lagrangian function with the fuel cost and emission such as NOx and SOx from power plants. The generation rescheduling searches for the solution that minimizes the Lagrangian function by using the Newton’s approach. While the Pareto optimum in the fuel cost and emission minimization has a drawback of finding a number of non-dominated solutions, the proposed approach can explore the non-inferior solutions of the multiobjective optimization problem more efficiently. The method proposed is applied to a 4-machine 6-bus system to demonstrate its effectiveness.

Generation Rescheduling Based on Energy Margin Sensitivity for Transient Stability Enhancement

Kim, Kyu-Ho,Rhee, Sang-Bong,Hwang, Kab-Ju,Song, Kyung-Bin,Lee, Kwang Y. The Korean Institute of Electrical Engineers 2016 Journal of Electrical Engineering & Technology Vol.11 No.1

This paper presents a generation rescheduling method for the enhancement of transient stability in power systems. The priority and the candidate generators for rescheduling are calculated by using the energy margin sensitivity. The generation rescheduling formulates the Lagrangian function with the fuel cost and emission such as NO_x and SO_x from power plants. The generation rescheduling searches for the solution that minimizes the Lagrangian function by using the Newton’s approach. While the Pareto optimum in the fuel cost and emission minimization has a drawback of finding a number of non-dominated solutions, the proposed approach can explore the non-inferior solutions of the multiobjective optimization problem more efficiently. The method proposed is applied to a 4-machine 6-bus system to demonstrate its effectiveness.

Task Rescheduling Using a Coordinator in a Structural Decentralized Control of Supervisory Control Systems

Sang-Heon Lee,Ill-Soo Kim,Kai C. Wong 한국정밀공학회 2004 International Journal of Precision Engineering and Vol.5 No.2

A problem of task rescheduling using a coordinator in a structural decentralized control of supervisory control theory is formulated. we consider that the overall system is divided into a number of local systems. Using an example of a chemical batch reaction process, it has shown that after local supervisors have been established for a given task, a coordinator can be used to solve some rescheduling problems among local plants for new or modified tasks. The coordination system models the interactions of local plants, and is consisting of only the shared events of local plants, so simpler to synthesize. A coordinator is designed based on the specifications given for the coordination system. Under the 'structural' conditions developed in this paper, the combined concurrent actions of the coordinator with the existing local supervisors will achieve the rescheduling requirements. Again since the conditions are structural (not specification-dependent), once the coordination architecture has been established, it can be used for a number of different tasks without further verifications.

Preventive Control for Transient Security with Generation Rescheduling Based on Rotor Trajectory Index

Kusum Verma,K. R. Niazi 대한전기학회 2015 Journal of Electrical Engineering & Technology Vol.10 No.2

The increasing need to improve transient security assessment of existing or forecasted operating conditions of networks by power system operators is major concern of the power system security monitoring problem at the Energy Management Systems. This paper proposes a preventive control of transient stability with generation rescheduling based on rotor trajectory index obtained using time domain simulations. This index may help power engineers in making operational decision and to obtain a generation configuration with better transient security dispatch. The effectiveness of the proposed methodology is demonstrated on IEEE 39-bus New England system for a three phase fault at different loading conditions with single and multiple line outage cases.