리소스가없는 슬롯을 찾는 알고리즘

나는 공장을위한 프로젝트 관리 앱을 디자인하고있다. 이 앱은 프로젝트 계획 초안을 작성해야합니다. 리소스가없는 슬롯을 찾는 알고리즘

나는 기계를 추적,

기계 가용성 및

교대 근무 시간을 전에 시작하지 마십시오 -

작업 의존 관계 : 작업을 예약하려면 응용 프로그램은 세 가지 조건을 확인해야 약혼 : machine_allocations 테이블 :

machine_allocations 
+------------+--------------+-----------------+---------------+ 
| machine_id | operation_id | start_timestamp | end_timestamp | 
+------------+--------------+-----------------+---------------+

근무 시간은 패턴을 따릅니다. 이것은 좋은 방법입니다,

function earliest_slot($machine_id, $for_duration, $no_sooner_than) { 
    // pseudo code 
    1. get records for the machine in question for after $no_sooner_than 
    2. put start and end timestamps into $unavailable array 
    3. add non-working times as new elements to the array 
    4. in a loop find timeslots which are not in the array 
    5. if a timeslot is found which is equal to or bigger than $for_duration, return that 
}

내 질문은 :

지금, 나는 함수 생각하고 작업을위한 가장 빠른 날짜와 시간을 찾는 방법은? 이 작업을 수행하는 더 간단한 방법이 있습니까?

출처

2011-08-27 Majid Fouladpour

한 번에 한 작업에 대해 가장 빠른 날짜 - 시간을 찾는 것이 최상의 결과를 제공하지 않을 수도 있습니다. 연산 A가 장시간 동안 기계 1을 사용하고, 연산 B가 단시간 동안 기계 1을 사용하고, 연산 C가 단시간에 기계 2를 사용하지만, 연산 C가 B 이후에 수행되어야하는 예를 고려하십시오.

이 경우 , 기계 1에서 A보다 먼저 B를 스케줄하는 것이 더 나으나, 사용자의 접근 방식이이를 달성하지 못합니다. 물론 이것을 관리하기 위해 소프트웨어를 작성하고 사용하는 것이 제안한 것보다 어려울 수 있으므로 추가 혜택을 누릴 가치가 있는지 여부를 결정해야합니다.

Scheduling, Job Shop Scheduling 및 Scheduling algorithm을 살펴보십시오.

먼저 작업 (예 : 종속성, 우선 순위, 마감일)에 대해 수집 할 수있는 정보의 종류를 생각한 다음 최상의 방법을 결정해야합니다.

귀하가 제안한 것과 같은 접근 방식이 귀하에게 적합하다는 것을 알 수 있습니다. 귀하가 제안한 알고리즘에 덧붙여 기존 기계 조작 목록을 정렬하여 빨리 검색 할 수 있습니다. 즉, 가장 빠른 시간으로 보장되기 때문에 조작이 적합한 시간을 찾자 마자 즉시 중지 할 수 있습니다.

상대적으로 단순한 확장은 우선 순위가 낮은 작업을 앞당기는 작업 (종속성 조정이 필요할 수도 있음)이 가능하지만 더 복잡한 알고리즘은 여러 작업을 한꺼번에 고려하여 최적화하려고합니다. 결과. 결국 그것은 당신의 특정한 문제에 적절한 것이됩니다.

출처

2011-08-28 01:50:04 Artelius

좋은 조언을 해줘서 고맙습니다. 나는 이렇게 생산 된 계획이 최적이 아니라는 것을 알고 있으며, 그것이 내가 '계획 초안'이라고 부르는 이유이다. 나는 고객이 시간표를 손으로 조정할 필요가 없다고 약속하지는 않는다. 그래서 복잡성을 억제하기 위해 접근 중입니다. 그래서 제한된 유틸리티 가격 *에 대해 제안 할 예정입니다. 알고리즘이 가장 간단하다는 것을 알 수 있습니까? –

나는 알고리즘이 중요하지 않기 때문에 충분히 간단하다고 생각한다. 간단한 해결책이있는 경우에, 특히 당신의 필요 조건이 변화 할지도 모른다 간단한 해결책을 찾는 시간을 낭비하지 말라. – Artelius

* 아주 좋은 통보 *의 또 다른 조각. 당신 말이 맞아요. 나는 그것을 구현하는 것이 좋습니다! - 나는이 마지막 것을 기억할 것이다 (나는 약속한다)). –

이는 작업 계획을 세울 때마다 다릅니다. 컴퓨터의 작업을 시작하기 전에 브랜치 & 바운드 알고리즘 또는 이와 비슷한 (mayby 동적 프로그래밍) 지점이있을 수 있습니다. 기계가 작동 할 때 작업을 계획해야하고 최적의 솔루션을 위해 어떤 작업이 수행되는지 알 수 없습니다. 계산할 수는 없습니다 (잘 생각할 수 없습니다). Mayby 최대 시간을 가진 기계에 다음 작업을 넣어? Mayby 역동적 인 버전의 Ford-Bellmas alg (당신이 생산의 두 개의 층을 가지고 있으면). 말하기 힘듭니다. 나는 2 개의 approches를하고 마녀가 최상인지 결정할 것이다. 당신은 이것에 대한 기사를 쓸 수 있습니다 :)

출처

2011-08-27 23:26:05

질문을 올바르게 읽지 않았다고 생각합니다. 가장 확실한 것은'earliest_slot' 함수를 구현하는 방법입니다. – svick

@neosatan 감사합니다. 각 작업은 가능한 첫 번째 시간에 계획되어야합니다. * 여기서 * 가능하다 : (i) 구매하기 전에 아이스크림을 먹지 말아야한다. (ii) 우리가 필요로하는 기계는 작업 기간 동안 무료 여야한다. 작업을 비 근무 시간으로 설정하십시오. –

@svick 나는 그것을 올바르게 읽었지만 취업에 들어가면 얻을 수있는 모든 정보는 매우 중요합니다. 내 생각에 질문이 정확하지 않으므로 여기에 일반적인 답을 달았습니다. Artelius는 아주 좋은 대답을했습니다. 나는 더 많은 정보를 얻고 싶었습니다. –

리소스가없는 슬롯을 찾는 알고리즘

답변

관련 문제