Railway Track Maintenance Scheduling using Artificial Bee Colony

Artificial Bee Colony 기법을 이용한 철도궤도 유지보수 일정계획 수립 연구

Railway Track Maintenance Scheduling using Artificial Bee Colony

남덕희

¹

·김기동

¹

·이성욱

²

·김성수

^†

Duk-Hee Nam

^·

Ki-Dong Kim

^·

Sung-Uk Lee

^·

Sung-Soo Kim

1. 서 론 1.1 문제정의와 연구의 목적

궤도유지보수분야의인력

,

^{장비등각종자원의능력과}

일정을감안하여가장 효율적이고효과적인유지보수 계획 을수립하는것을유지보수일정최적화라한다

[4].

^효율적이

고효과적인유지보수계획이란여러가지로설명될수 있 다

.

^{유지보수를수행하는단체의목적이나상황에따라그}

기준은달라질 것이다

.

그러나결국 한정된자원을이용하 여적절한시기에더많은 작업을수행하는것은 유지보수 일정최적화의가장일반적이고범용적인목적이라할수있 다

.

현재철도궤도의유지보수작업현장은각자의성격에따 라다양한방법을 통하여이루어지고있다

.

^{따라서일정계}

획시 반영해야하는 현장의상황들도다양한차이점을보 이고있다

.

^{본논문에서는 이러한상황에유연하게 대처하}

고보다빠르게일정을수립하게위하여휴리스틱알고리즘 을 적용한 방법론을 제안 하고자 한다

.

휴리스틱알고리즘은최적해를보장할수는없지만

,

빠

른 시간내 또는 사용자가제시하는시간내에최적해 또 는 최선해를 제시할 수있다

.

뿐만아니라 다양한문제를 보다쉽게 적용하여풀이할수있다는 장점도가지고있다

.

따라서다양한철도궤도유지보수현장의다양한상황들도 보다 수월하게 반영하여 최적화 할 수 있다

.

그 중에서

Artificial Bee Colony Algorithm (ABC)

은

2005

년 이후부터 활발히연구

[9]

가진행되고있고그 성능에대하여입증되 었으며자원할당과일정계획분야에도그연구가활발히진

행 중이다

[2,3].

본논문의목적은철도궤도유지보수일정계획문제를수 리모델화하고

BABC

메커니즘을한국철도공사의고속선궤

도 보수이력데이터

[7,8]

^{를사용하여 궤도유지보수일정최}

적화문제의 최선해를찾아내는 것이다

.

본 논문의

2.1

절 에서는궤도유지보수일정계획문제를설명하고

,

목적식과 제약조건의수리모형을설정하였다

. 2.2

절과

2.3

절에서는궤

도 유지보수일정계획문제에

BABC

^{를 적용하는메커니즘}

에 대하여서술하였다

.

그리고

3

절에서

BABC

를이용하여

일정계획문제를풀이하였고그결과를최적화하고분석하 였다

.

1.2 관련 연구 현황

현재여러분야에서사용되고있는자원할당문제나일정 계획 문제는궤도 유지보수일정최적화문제의한방법이 될 수 있다

.

본 논문에서다루고있는궤도 유지보수일정 Abstract

The objective of this paper is to propose a fast and easy Binary Artificial Bee Colony (BABC) heuristic algo- rithm to optimize NP-hard scheduling problem of railway track maintenance considering real conditions

.

The optimal or best solutions can be found using proposed BABC within very short or user specified computation time. We can greatly maximize the objective value using this proposed method in 30, 60, 100 and 200 work size railway track maintenance scheduling problems for experiment and analysis.

Keywords

: Railway track maintenance, Artificial Bee Colony

초 록 본 논문의 목적은 보다 빠르고 수월하게 현장의 상황을 반영하여

NP-hard

철도 궤도 유지보수 일정계

획을 최적화할 수 있는

Binary Artificial Bee Colony Algorithm (BABC)

휴리스틱 알고리즘을 제안하는 것이다

.

본 논문에서 제시하는 방법을 사용하여 빠른 시간 또는 사용자가 제시하는 시간 내에 최적해 또는 최선 해를

제시할 수 있다

.

본 논문에서 제안하는 방법을 사용하여

30, 60, 100, 200

개 작업의 궤도 유지보수 일정계획 문

제의 실험 및 분석을 통하여 목적식 값을 최대화할 수 있었다

.

주요어 : 궤도유지보수일정계획

, Artificial Bee Colony

†

교신저자 : 강원대학교 공과대학 산업공학과

E-mail : [email protected]

1

강원대학교 공과대학 산업공학과

2

한국철도공사

계획의문제에서는단일 공정작업을수행할수있는 다수

개의자원이존재하므로일정계획문제의

parallel machine

problem (

병렬기계문제

)

문제에해당한다

[10].

다수의기

계에서각각의 할당작업과작업의처리순서를 결정하는

Nonpreemptive parallel scheduling problem

중

Completion

time

을최대화하는문제는

NP-hard

로 알려져있고

[11],

이

는본 논문에풀이하고자하는 일정계획 문제와일맥상통 한다 할 수 있다

.

병렬기계의일정계획에대한연구는

60

년대이후부터활

발히진행 되어왔다

. Li[12]

는 비 동일 병렬기계의 총 가

중완료시간을최소화하는문제의모델에대하여정리하

였으며

, McNaughton[13]

은동일병렬기계에서최대작업완

료시간

(makespan)

을최소화하는알고리즘을개발하였다

.

궤도유지보수일정계획문제와관련하여오석문

[5]

은도 상다짐작업의장기일정계획문제에대하여상용프로그램

에탑재할수있는모형을제시하였고

, Masashi MIWA[14]

는

MTT

^{의 도상다짐작업의일정계획문제를유지보수 비}

용의최적화측면에서풀이할수있는모형을제시하였다

.

그러나궤도유지보수 분야는현장의 많은상황들이제약 으로존재하고있고

,

이를기존의문제에적용하기에는 많 은어려움이있다

.

또한현장의종류나특성에 따라현장의 상황이모두다르기때문에적용되어야할제약에도차이가 있다

.

^{본논문에서는현장조사와관련자료의 분석을통하}

여각현장에서공통적으로반영되어야할제약에대하여정 의하였다

.

이는각 현장의상황에맞는일정계획의기본이 될수있으며

,

정의된제약을적용한방법론역시현장의상 황에따라발생하는제약을 적용할 수 있는바탕이 될 수 있다

.

2. 문제 분석 및 알고리즘 개발 2.1 궤도 유지보수 일정계획 문제

궤도유지보수작업은각각작업종류와완료요구일

,

작 업구간그리고작업시간이존재한다

.

작업종류는궤도의 이상상태에 따라결정된다

.

그종류로는인력템핑

,

장비템

핑

(Spot,

총다지기등

),

자갈정리

,

장대재설정

,

레일육성용

접 등 여러가지가 있지만인력 및 장비템핑이작업량의 대부분을차지하고있다

.

이러한작업들은보통그 종류별 로 수행할수있는자원의 종류가정해져있다

.

인력템핑 은일반적으로인력팀이작업을수행한다

.

장비템핑은

Spot

템핑과총다지기로구분할수있는데이 둘을구분하는정 확한기준은존재하지않는다

.

하지만현장에서는일반적으 로작업의연장이비교적긴경우전체도상다짐을위해총 다지기를수행하고작업의연장이짧고

,

부분적인도상다짐

이 필요한 경우

Spot

템핑을 수행 한다

[7].

총다지기는보통

MTT(Multiple Tie Temper)

를통하여작

업을수행 한다

. MTT

란자갈궤도의궤도틀림정정 작업에

가장많이사용되는도상 다지기용 장비이다

. MTT

는 보

통유압을통한

Temping Bar

의상하작용을통하여수평방

향의다지기작업을수행한다

. Spot

템핑은보통

STT(Switch

Tie Temper)

를 통하여작업을 수행한다

. STT

는 원래선로

의

3

대취약점

(

곡선부

,

이음매부

,

분기부

)

의하나인분기부 를 다지기위한장비이다

.

그러나분기기뿐아니라일반적 인 구간에서도작업이가능하므로 현장에서는전구간에서 유용하게 사용 되고 있다

[6].

이처럼궤도유지보수현장에서는 각작업종류에따라이 를 수행할수 있는 자원이일반적으로정의되어있지만작 업 환경이나작업자의경험에따라다르게설정할수도있

다

.

예를들어

Spot

템핑은일반적으로

STT

장비가 수행하

지만작업자의의도에따라인력자원으로혹은

STT

또는인 력 자원중 어떠한 것이할당되어도 좋다라고설정할 수 도 있다

.

따라서 궤도유지보수일정계획은각작업종류에 따라 사용자가미리정해놓은작업을수행할수 있는자원 을 고려하여 계획을수립할 수있어야 한다

.

그러므로일 정 계획결과작업에 할당되는자원은작업종류와작업자 가 미리정해놓은수행가능한자원과의관계에의하여결

정된다고 할 수 있다

[7,8].

완료요구일은 작업이수행 되어야하는 최종일로서자원 의 용량이허용하는한도 내에서는반드시완료 요구일이 내에작업이이루어져야한다

.

작업구간은선로점검차량또 는 선로점검자의궤도점검결과보수가필요하다고생각되 는 구간의시점과종점을의미한다

.

시점부터종점까지의 거리를연장이라하며

,

^{이는작업의시간과도관련이있다}

.

^대

부분의 작업시간은작업종류별 작업속도와작업의연장을 고려하여정해지는데궤도의특성이나

,

작업환경등을고 려하여 유동적으로설정될 수 있다

.

일정수립기간은작 업을수행 하고자하는기간을의미하는데

,

^{이기간에완료}

요구일이포함되어있는작업들은일정수립의대상이된다

.

2.1.1 파라미터 설정

본절에서는목적함수와제약식을표현하기위한결정변 수와파라미터를설정한후목적함수와제약식에대하여기

술 하였다

.

이와관련하여

2.3

에서는

30, 60

개작업구간을

대상으로각작업을 j로설정하고인력팀

, MTT, STT

을자

원 r로

, 7

일의할당 일을t로 설정하여 이에대한 실험및 분석을 상세히 설명 하였다

.

-

결정변수

x

_jtr =

^j작업이

^{t기간에r자원을}이용하여실시되면

1,

아니 면

0

ld

rt =

r자원이t기간에실시할작업 중가장먼거리에위 치한 작업 구간의 종점

sd

_rt =

^{r자원이 t기간에}실시 할작업 중가장가까운거리 에 위치한 작업 구간의 시점

-

파라미터 정의

j

=

작업번호

(1

≤j ≤ J

)

t

=

^{기간 인덱스}

(1

^{≤t ≤ T}

)

r = 자원 번호

(1

≤r ≤ R

)

F

_j =

^{j작업 구간의 시점}

T

j =

j작업 구간의 종점

2.1.2 목적함수와 제약조건

본논문에서풀이하고자하는 궤도유지보수일정계획문

제는

Binary Integer Programming

문제이다

.

이를목적함수

와 제약조건을 통하여 아래와 같이 표현하였다

.

작업시기를놓친 구간은이상상태의 진전으로인하여많 은추가비용을발생시킨다

.

뿐만아니라할당된 작업을모 두수행하지못할 경우추가인력이나장비에대한비용이 발생한다

.

궤도유지보수일정최적화문제의목적함수는식

(1)

과 같이적절한시기에 최대한많은작업을 수행하는것

이다

[1].

(1)

궤도유지보수작업에는일정 계획 시고려해야하는 여 러가지현실적인상황이존재한다

.

궤도유지보수일정최 적화를위하여현장의일반적인상황을다음과같은제약으 로 표현 할 수 있다

.

각보수작업은일정수립기간중단 하루에만

,

그리고단 하나의자원에만할당되어야한다는제약을식

(2)

^와같이

나타낼 수 있다

[8].

(2)

각보수작업은해당작업을수행할 수 있는자원에의 해서만수행될 수 있다는제약을식

(3)

^과식

(4)

^{와 같이나}

타낼 수 있다

[8].

(3)

(4)

할당된모든작업은완료요구일안에이루어져야한다

는 제약을 식

(5)

와 식

(6)

과 같이 나타낼 수 있다

[8].

(5)

(6)

인력작업시 하루최대이동거리내에서모든작업이이 루어 져야한다는제약을 식

(7)

을 통하여 나타낼 수있고

,

작업 준비시간과 작업정리시간그리고작업개소간 이동 시간을포함한하루의작업시간은최대작업시간 내에이루 어 져야한다는제약을식

(8)

을통하여 나타낼수있다

[8].

인력이나 작업을운영할수 없는날 C

rt

−RA

h

는 음수값 을 가질수있으므로

Max

를취하여음수값으로인한제약 의 오류를 방지 하였다

.

(7) (8)

작업 준비시간과작업 정리시간그리고작업을위한총 이동 시간을포함한하루의작업시간은최대작업시간내 에 이루어져야한다는 제약을식

(9)

와 같이나타낼수 있 다

[8].

(9)

각 자원에할당된작업의최대

,

최소 거리를파악하여자 원의가용일별작업구간을산출하기위한식을식

(10)

과식

(11)

^{과 같이 나타낼 수 있다}

[8].

(10) (11)

2.2 BABC 메커니즘 설명

ABC

를활용한

Binary ABC

를궤도유지보수일정계획문

제에적용하여어떻게최적해

/

^{최선해를탐색해낼수 있}

는지

Fig. 1

과 같이

BABC

흐름도로설명할 수 있다

.

단계

1

^에서는

Food source, Employed bee, Onlooker bee

^{의 수}

(SN), Limit(

이웃해 탐색최대 수

),

종료조건을 결정한다

.

단계

2

에서는초기가능해군을생성하기 위하여특정자원이 특정작업에할당되었을때는

1,

아니면

0

으로하는초기

해

(BABC

^에서

Food source)

^{들을 생성하여초기해군}

(initial

population)

을 생성한다

.

단계

3

에서는각 초기해에대하여

Employed bee

^{를결정하고각초기해들의지역탐색을위하}

여 이웃해를 탐색한다

.

각해에대하여 더좋은 해가생성

되면더 좋은해로업데이트하면서

Trial(

이웃해탐색시도

횟수

)

을

0

으로설정하고그렇지않을경우해당

Food source

의

Trial = Trial + 1

^{로 증가시킨다}

.

^단계

4

^{에서는단계}

3

^의모

든 해의이웃해탐색후 갱신된초기해군의모든해를사 D

_j =

^{j작업의 완료 납기일}

P

rj =

r자원을이용하여

j작업을수행할경우수행시 간

(

단위

:

분

)

SR

_j =

^{j작업을 수행 할 수 있는 자원들의 집합}

SJR

r

= r자원을이용하여수행할수 있는작업들의집합 C

_rt =

^{r자원의 t기간 작업 가능 시간}

(

^단위

:

^분

)

RA

h =

인력자원의 작업여유시간

(

준비시간

+

이동시 간

+

정리시간

)

RA

_m =

^{장비자원의 작업여유시간}

(

^준비시간

+

^이동시

간

+

^정리시간

)

SMR

m =

장비 자원들의 집합 SHR

_h =

^{인력 자원들의 집합}

LT

r =

r자원의최대이동가능거리

,

인력자원만해당됨 BigM

=

^대수

M

Max x _jtr r = 1

∑ R t = 1

∑ T J = 1

∑ J

x _jtr ≤

1

, ∀ j r = 1

∑ R t = 1

∑ T

x _jtr ≤

1

, ∀ j r SR ∈ ∑

j

t = 1

∑ T

x _jtr ≤

0

, ∀ j r SR ∉ ∑

j

t ^{= 1}

∑ T

x _jtr ≤

1

, ∀ j r = 1

∑ R t D ≤ ∑

j

x _jtr ≤

0

, ∀ j r = 1

∑ R t D > ∑

j

ld _rt

–

sd _rt ≤ LT _r ∀ r t , ∀

P _rj ⋅ x _jtr ≤

max

( C _rt

–

RA _h ,

0

) r SHR , ∈ _h , ∀ t j SJRr ∈ ∑

P _rj ⋅ x _jtr ≤

max

( C _rt

–

RA _m ,

0

) r SHR , ∈ _m , ∀ t j SJRr ∈ ∑

T _j ⋅ x _jtr ≤ ld _rt , ∀ j t t , ∀ , ∀

F _j

+

BigM ⋅ (

1–

x _jtr ) ≥ sd _rt , ∀ j t t , ∀ , ∀

용하여평가값

(

i 번째

Food source

의 평가값 f

i )

에비례하

는확률로해

(Food source)

를 선택하여이해의이웃해와비

교하여 더좋은 해가생성되면더 좋은해로 업데이트하

면서

Trial

을

0

으로설정한다

.

그렇지않을경우단계

3

과같

이

Trial

를 증가시킨다

.

단계

5

에서는

Trial

이

Limit

보다 같

거나클 경우해당

Food source

는 더 이상 탐색하지않고

탈락시킨다

.

탈락시킨해의수만큼의새로운해를

Scout bee

를통하여임의적으로생성하여지역해

(local solution)

에빠 지지않고다양한 해탐색을 추구함으로써 전역해

(global

solution)

를 탐색할 수 있도록 한다

.

이 모든 단계수행 후

종료조건

(

세대수

,

사용자가제시한시간제한등

)

에맞으면

종료하고그렇지않으면

Employed bee

의 이웃해생성부터

반복 시행한다

[2,3].

2.3 궤도 유지보수 일정 계획 문제에 BABC 적용

본

2.3

^절에서는

2.2

^{절에서설명한}

BABC

^{메커니즘을간단}

한예제를이용하여궤도유지보수일정최적화문제에어떻 게적용할수 있는지에대하여기술하였다

.

^{예제데이터는}

한국철도공사의고속선궤도보수이력데이터를참고하여 가정한 것이다

.

2.3.1 궤도 유지보수 일정 예제 문제

아래의

Table 1

은예제문제의정보를정리한 데이터이

다

.

^{먼저일정수립 기간은}

3

^월

1

^일과

3

^월

2

^{일 모두이틀간}

의 일정을 수립한다

.

가용 자원은 장비 자원으로

MTT

와

STT

^{각각한대그리고 한개의 인력팀을대상으로한다}

.

각자원의수행가능한작업은

MTT

는 작업종류

1

과작업종

류

2, STT

는 작업종류

2,

인력 팀은작업종류

3

을 수행한

다 가정 하였다

.

2.3.2 예제 문제 풀이 절차

BABC

^{를 적용한궤도유지보수일정문제풀이는파라}

미터초기화

,

초기해생성

, Employed bee

에의한이웃해탐

색

, Onlooker bee

에 의한전역해탐색

, Scout bee

에의한새

로운해 탐색의절차로이루어진다

.

가장먼저문제풀이에 필요한파라미터들을미리설정한다

. BABC

알고리즘에문

제를 적용하기 위해서

Food source

와

Employed bee,

Onlooker bee

의개수

,

그리고

Limit

와종료조건이필요하다

.

초기

Food source

생성을위하여 의사결정변수 x

_jtr

을 표

현하기 위해본 논문에서는 작업별 가용일과작업별 자 원이라는두 개의의미를 담을 수 있도록해를표현 하였

다

.

아래

Fig. 2

의 x

jtr

는 작업 j가 t기간에r의 자원을 이용

하여실시되면

1

의값을

,

그렇지않으면

0

의값을가지게된 다

.

다음

Fig. 2

는

Table 1

예제 데이터의

Food source

표현 방법을 나타낸 것이다

.

이와같은해 표현기법을통하여해표현가능영역과불

가능영역을설정할수있다

.

해표현 불가능영역이란

Fig.

3

과 같이각 작업 별로주어진 완료요구 일의범위 밖의

날과 해당작업을수행 할 수 없는자원의 영역에의사결 정변수x

jtr

가 아닌

0

의 값을 미리할당하는영역을말한다

.

초기해를생성하기위하여각 작업별로해 표현가능 영역중 하나의영역을임의적으로선택한다

.

선택된영역 은

1

의 값을가지게되고해표현불가능영역을포함한나 머지영역은

0

의 값을갖게된다

.

초기해생성후장비와인 력 자원의용량 제약을고려하여미리설정하기어려운제

약들은 해의값이제약을 만족시킬수 있도록

2.3.3

의 가

능해 탐색 절차를 수행 한다

.

Employed bee

에 의한 이웃해 탐색은

Food source

의 모

든 작업중 임의적으로 선택된 하나의 작업에대하여 다 른 날또는다른 자원으로할당결과를변경하는것이다

.

이 Fig. 1

Flowchart of BABC[2,3]

Table 1

Example data for 16 work size

작업 번호 작업

종류 시점

(m)

^종점

(m)

^연장

(m)

^작업시간

(

분

)

^{완료요구일}

(net)

J1 3 10 13 3 30 3

월

2

일

(2)

J2 3 5 9 4 40 3

월

2

일

(2)

J3 3 1,927 1,930 3 30 3

^월

2

^일

(2)

J4 3 422 432 10 80 3

월

2

일

(2)

J5 3 2,500 2,575 25 100 3

월

2

일

(2)

J6 3 617 620 3 30 3

월

2

일

(2)

J7 1 3,000 3,080 80 60 3

^월

2

^일

(2)

J8 1 105 135 30 30 3

월

2

일

(2)

J9 2 990 1,000 10 10 3

월

2

일

(2)

J10 2 305 310 5 5 3

월

2

일

(2)

J11 3 3,044 3,053 9 90 3

^월

2

^일

(2)

J12 1 200 219 19 20 3

월

2

일

(2)

J13 2 3,077 3,097 20 40 3

월

2

일

(2)

J14 3 2,233 2,243 10 30 3

월

2

일

(2)

J15 1 3,120 3,125 5 50 3

^월

1

^일

(1)

J16 2 1,997 2,020 23 100 3

월

1

일

(1)

때 변경 될 작업은 다른

Food source

의 할당 결과를 모방 하여변경하게 된다

.

이웃해탐색의 절차는 다음과같다

.

단계

1 :

이웃 해를 탐색 할 자기 자신을 제외한

Food

source

중 하나를 임의적으로 선택

단계

2 :

선택된

Food source

의 모든작업 중 하나의 작

업

j

를 임의적으로 선택

단계

3 :

선택된작업 j에포함된모든 x

jtr

의할당값을자

기 자신의

Food source

의 x

_jtr

값으로 변환

단계

4 :

가능 해 탐색 절차 수행

단계

5 :

기존의평가 값보다좋으면채택 후

Trial

를

0

으

로

,

그렇지 않으면 탈락 후

Trial+1

단계

6 :

자기자신이마지막

Food source(SN)

이면종료

,

그렇지 않으면 단계

1

로

Onlooker bee

의 전역해탐색은모든

Food source

의평가

값을바탕으로새로운이웃해를탐색하는것이다

.

각

Food

source

는 아래의식

(12)

에따라 자기자신이 선택될 확률

을갖는다

.

선택된

Food source

만이이웃해를탐색할수있

으므로 결국 좋은평가 값을 가지는

Food source

는 더 많

은 이웃해탐색의기회를 갖게되는것이다

.

이후의이웃

해탐색과정은

Employed bee

^{에의한이웃해 탐색과동일}

하다

.

전역해 탐색과정에서

Food source(

i

)

가 선택될 확

률

(

p

i )

는 식

(12)

와 같다

.

(12)

위의이웃해 탐색과정에서각

Food source

^{별로업데이}

트 되고있는

Trial

을 미리설정된

Limit

와비교한다

. Trial

이

Limit

만큼커지면해당

Food source

는미리정해진세대

수 동안더 좋은해를찾지못한것이므로이 해는버려지

게 되고버려진

Food source

^의수만큼

Scout bee

^{에 의하여}

새로운해를탐색한다

.

새로운해를탐색하는방법은초기

해 생성과 동일하다

.

이 모든단계수행후 종료조건

(

본논문에서는 세대수로 함

)

에 맞으면종료하고그렇지않으면이웃해생성부터반 복 시행한다

.

2.3.3 가능해 탐색 절차

초기해와이웃해탐색후만들어진해는 식

(7),

식

(8),

그

리고식

(9)

를만족한다고할수없다

.

식

(7),

식

(8)

그리고식

(9)

를 만족하지못하는해는비가능해라 할수있으므로이

러한비 가능해를가능해로만들기위한절차는반드시필

요하다

.

궤도유지보수일정계획문제에서순수한

BABC

의

해 탐색을통하여얻어질수있는해들은매우많은비 가 능 해를포함한다

.

뿐만아니라작업할당량을최대화하기 위하여 더많은비 가능해를탐색하게될 것이다

.

따라서 초기해와이웃해탐색후 만들어진해는 아래의가능해탐 색 절차를통하여 가능해로변경되게된다

.

식

(7)

의제약식 을 만족하기 위한 가능해 탐색 절차는 다음과 같다

.

단계

1 :

자원r에대하여t날할당된작업들중 ld

rt

와 sd

rt

찾기

, loop = 0

단계

2 :

ld

rt

−sd

rt

의 값을구하여 LT

r

보다크면

loop

에

1

을 더한 후 단계

3

으로

,

그렇지 않으면 단계

4

로

단계

3 : loop

가 홀수이면ld

rt

에 할당된 작업x

jtr

의 값을

0

^으로

, loop

^가짝수이면 sd

rt

에할당된작업 x

jtr

의값을

0

^으

로 할당한 후 단계

1

로

단계

4 :

^t

=

^T이면 단계

5

로

,

그렇지 않으면단계

1

로이 동 후 t

=

t

+ 1

단계

5 :

^r

=

^{R 이면종료}

,

^{그렇지않으면단계}

1

^{로 이동}

후 r

=

r

+ 1,

t

= 1

식

(8),

^식

(9)

^{의 제약식을만족하기 위한가능해 탐색절}

차는 다음과 같다

.

단계

1 :

^{자원r에 대하여 t날 할당된 모든 작업들의작}

p _i f _i f _n n = 1

SN ∑

=

⁄

Fig. 2

Representation of Food source

Fig. 3

Representation of Food source considering constraints