http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
- 中文 을 입력하시려면 zhongwen을 입력하시고 space를누르시면됩니다.
- 北京 을 입력하시려면 beijing을 입력하시고 space를 누르시면 됩니다.
RISS 인기검색어
- 검색키워드
- 저자 : ( Inna G. Drobouchevitch ) (검색결과 2 건)
- 무료
- 기관 내 무료
- 유료
-
Three-machine Open Shop Problem with the Minimum Makespan Criterion
Inna G. Drobouchevitch 한국생산관리학회 2016 韓國生産管理學會誌 Vol.27 No.1
본 논문은 삼중기계 오픈샵 일정계획의 makespan 최소화 문제(O3||Cmax), 즉 최대 총공정시간 최소화 문제를 다룬다. 이중기계 오픈샵 문제의 다항시간 알고리즘과 그 해는 Gonzalez와 Sahni에 의해 이미 도출되었다. Gonzalez와 Sahni는 이러한 문제가 삼중기계 조건으로 확장되었을 때, NP-hard 문제로 분류됨을 증명하였다. 때문에 문제의 복잡도 측면을 고려한다면 보다 효율적인 알고리즘이 구현 가능한 또 다른 NP-hard 분류 범위를 탐색해 볼 필요가 있다. 본 연구는 O3||Cmax 문제의 NP-hard 분류가 가능한 범위를 최대공정시간과 기계부하의 관계를 통해 공식화한다. Li을 i번째 기계의 부하(총공정시간), pmax을 최대공정시간으로 정의하고, 기계의 번호(i)는 부하의 단조감소 순서에 따라 부여한다고 하자. 이때 L₁-L₃ ≥ 2pmax의 조건에서 O3||Cmax 다항시간 알고리즘 문제의 최적해가 도출될 수 있음이 밝혀진 바 있다. 본 연구에서는 ‘hard’ 문제와 ‘easy’ 문제의 명확한 구분을 위해 매개변수분석을 수행한다. 이에 따른 주요한 결과로 2L₁-L₂-L₃ <2pmax의 조건이 만족할 때 일반적인 NP-hard 문제로 분류 가능함을 보여준다. 분석결과는 또한 여전히 일반적인 O3||Cmax 문제의 복잡도가 판단될 수 없는 분류 범위를 도출하였다. 이와 같은 범위에서는 NP-hardness의 범위를 벗어나는 특수한 O3||Cmax 문제를 제안하여 선형시간 조건 하에서 최적해 도출이 가능함을 확인한다. The paper considers the three-machine open shop scheduling problem to minimize the makespan, i.e., the maximum completion time (O3||Cmax). The open shop problem was introduced by Gonzalez and Sahni who gave a polynomial time algorithm for its solution in the case of two machines. They also proved that this problem is NP-hard in the case of three machines. In view of the problem complexity, it is an attractive research goal to search for the widest possible classes of problem instances which admit efficient solutions. Such problem classes can be formulated in terms of a certain relation between machine loads and maximum operation length. Let Li be the load (the total time of all operations) of the ith machine and let pmax be the maximum operation length. Suppose that the machines are numbered in the non-increasing order of their loads. The O3||Cmax problem is known to be polynomially solvable if L₁-L₃ ≥2pmax. In this paper, we show that the problem is ordinary NP-hard if 2L₁-L₂-L₃ < 2pmax. We then consider a special case of the O3||Cmax problem that lies outside the known NP-hardness bounds and show that it is solvable in linear time.
-
On the problem of movie selection and scheduling to maximize revenue
( Inna G. Drobouchevitch ) 한국생산성학회 2015 生産性論集 Vol.29 No.4
We consider a problem of the selection and scheduling of movies for a multiplex (i.e., a theater with multiple screens) to maximize the exhibitor``s cumulative revenue over a fixed planning horizon. Effective and timely decisions on screen management directly and crucially relate to the effective capacity and resources usage, productivity and successful economical performance of the theater. In the problem under study, the release times of the movies that can potentially be selected during the planning horizon are known a priori. If selected for screening, a movie must be played continuously through its obligatory duration, after which its run may or may not be extended. The problem involves two primary decisions: (i) the selection of movies to play and (ii) the determination of the duration of screening for the selected movies. We show that revenue optimization problem under the preempt-resume policy is strongly NP-hard even in the minimal case, thus completely resolving the complexity status of the problem. We also consider the optimization problem under the non-preempt policy for a case of unequal screen capacities and show that an optimal solution may significantly differ from the solution obtained for the equal-capacity case.
연관 검색어 추천
이 검색어로 많이 본 자료
활용도 높은 자료
