본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

다수의 경쟁이 존재하는 환경에서 적시 스케줄링에 관한 연구
Just-in-time Scheduling with Multiple Competing Agents

정대영    (JDA 소프트웨어   ); 최병천    (충남대학교 경영학부  );
  • 초록

    We consider a multi-agent scheduling problem such that each agent tries to maximize the weighted number of just-in-time jobs. Two objectives are considered : the first is to find the optimal solution for one agent with constraints on the other agents' weight functions, and the second is to find the largest set of efficient schedules of which corresponding objective vectors are different for the case with identical weights. We show that when the number of agents is fixed, the single machine case with the first objective is NP-hard in the ordinary sense, and present the polynomial- time algorithm for the two-machine flow shop case with the second objective and identical weights.


  • 주제어

    Multi-Agent Scheduling .   Just-in-Time job .   Efficient Schedule.  

  • 참고문헌 (16)

    1. Agnetis, A., P.B. Mirchandani, D. Pacciarelli, and A. Pacifici, "Scheduling problems with two competing agents," Operations Research, Vol.52, No.2(2004), pp.229-242. 
    2. Agnetis, A., P.B. Mirchandani, D. Pacciarelli, and A. Pacifici, "Multi-agent single machie sheduling," Annal of Operations Research, Vol.150(2007), pp.3-15. 
    3. Ahuja, R.A., K. Mehlhorn, J.B. Orlin, and R.E. Tarjan, "Faster algorithms for the shortest path problem," Journal of the Association for Computing Machinery, Vol.37(1990), pp.213-223. 
    4. Arbib, C., S. Smriglio, and M. Servilio, "A competitive scheduling problem and its relevances to UMTS channel assignment," Networks, Vol.44, No.2(2004), pp.132-141. 
    5. Cepek, R.L. and S.C. Sung, "A quadratic time algorithm to maximize the number of just-in-time jobs on identical parallel machines," Computers and Operations Research, Vol.32(2005), pp.3265-3271. 
    6. Cheng, T.C.E., C.T. Ng, and J.J. Yuan, "Multi-agent scheduling on a single machine to minimize total weighted number of tardy jobs," Theoretical Computer Science, Vol.362(2006), pp.273-281. 
    7. Choi, B.C. and S.H. Yoon, "Maximizing the weighted number of just-in-time jobs in flow shop scheduling," Journal of Scheduling, Vol.10(2007), pp.237-243. 
    8. Cormen, T.H. and C.E. Leiserson, "Introduction to algorithm, Cambridge : MIT press, 1996. 
    9. Hall, N.G. and C.N. Potts, "Rescheduling for New Orders," Operations Research, Vol.52(2004), pp.440-453. 
    10. Hiraishi, K., E. Levner, and M. Vlach, "Scheduling of parallel identical machines to maximize the weighted number of just-in-time jobs," Computers and Operations Research, Vol.29(2002), pp.841-848. 
    11. Lann, A. and G. Mosheiov, "Single machine scheduling to minimize the number of early and tardy jobs," Computers and Operations Research, Vol.23(1996), pp.769-781. 
    12. Lee, K.B., B.C. Choi, J.Y.T. Leung, and M.L. Pinedo, "Approximation algorithms for multiagent scheduling to minimize total weight completion time," Information Processing Letters, Vol.109(2009), pp.913-917. 
    13. Lee, W.C., S.K. Chen, C.W. Chen, and C.C. Wu, "A two-machine flowshop problem with two agents," Computers and Operations Research, Vol.109(2009), pp.913-917. 
    14. Leung, J.Y.T., M.L. Pinedo, and G. Wan, "Competitive two-agent scheduling and its applications," Operations Research, Vol.58(2010), pp.458-469. 
    15. Ng, C.T., T.C.E. Cheng, and J.J. Yuan, "A note on the complexity of the problem of two-agent scheduling on a single machine," Journal of Combinatorial Optimization, Vol.12(2006), pp.387-394. 
    16. Sung, S.C. and M. Vlach, "Maximizing weighted number of just-in-time jobs on unrelated parallel machines," Journal of Scheduling, Vol.8(2005), pp.453-460. 
  • 이 논문을 인용한 문헌 (2)

    1. Shin, Moonsoo 2013. "Employment Contract-Based Management Model of Production Resources on Relation-Driven Fractal Organization" 대한산업공학회지 = Journal of Korean institute of industrial engineers, 39(4): 278~289     
    2. Lee, Moongul ; Seo, Sanghoon 2014. "A Study of Flight Scheduling Problem on Fighter Squadron" 한국경영과학회지 = Journal of the Korean Operations Research and Management Science Society, 39(2): 37~48     

 저자의 다른 논문

  • 최병천 (6)

    1. 2011 "오버레이 멀티캐스트에서 멀티미디어 스트리밍 서비스를 위한 최적 속도 할당에 관한 연구" 한국경영과학회지 = Journal of the Korean Operations Research and Management Science Society 36 (2): 33~42    
    2. 2013 "불확실한 환경 하에서 중간 평가가 있는 시간-비용 프로젝트 문제" 한국경영과학회지 = Journal of the Korean Operations Research and Management Science Society 38 (2): 25~42    
    3. 2013 "수리 모형을 이용한 조선 산업에서의 블록 적치장 최적 운영 계획 도출" 經營 科學 = Korean management science review 30 (3): 99~111    
    4. 2014 "순서 독립적인 셋업타임을 가진 동일작업의 병렬기계 배치스케줄링" 한국경영과학회지 = Journal of the Korean Operations Research and Management Science Society 39 (3): 83~91    
    5. 2015 "Min-Max Regret Version of an m-Machine Ordered Flow Shop with Uncertain Processing Times" Management science and financial engineering : MSFE 21 (1): 1~9    
    6. 2018 "A time-cost tradeoff problem with multiple interim assessments under the precedence graph with two chains in parallel" 韓國컴퓨터情報學會論文誌 = Journal of the Korea Society of Computer and Information 23 (3): 85~92    

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 이용한 콘텐츠
이 논문과 함께 출판된 논문 + 더보기