An Assembly Flow-Shop Scheduling Problem with SequenceDependent Setup and Transportation times

S. Ebrahimnejad*, R. Tavakkoli-Moghaddam, S. Hatami, Y. Maboudian

S. Ebrahimnejad, Assistant Professor of Industrial Eng – Islamic Azad University Karaj Branch
Tavakkoli-Moghaddam, Professor of Industrial Eng College of Engineering – University of Tehran
Hatami , M.Sc. of Industrial Eng – Islamic Azad University Ghazvin Branch Y. Maboudian, M.Sc. of Industrial Eng – Khaje Nasir University of Technology

Keywords ABSTRACT

1268732040128Downloaded from ijiepm.iust.ac.ir at 16:19 IRST on Saturday November 4th 2017

Downloaded from ijiepm.iust.ac.ir at 16:19 IRST on Saturday November 4th 2017

Three-stage assembly flowshop,
Scheduling,
Setup and Transportation Times, Enumeration technique. In this paper, three-stage assembly flowshop scheduling is considered with respect to minimizing bi-objectives, namely mean flow time and mean tardiness. This problem is a model of production systems, which several production operations are done simultaneously and independently, and then produced components are collected and transferred to an assembly stage for the final operation. In this model, by considering sequence-dependent setup time and components transformation times in order to make a real situation for the considered model, a lower bound (LB) is introduced to completion times of all the jobs. Further, due dates are generated randomly in a determined interval for some examples. To validate the proposed model, the Lingo 8.0 software and an enumeration technique that is coded in MATLAB are used. Comparison between the results of the Lingo 8.0 and enumeration technique shows that in larger problems (say n>8, where n is the number of jobs) the results obtained by Lingo do not have the good efficiency and cannot be compared with the enumeration technique in terms of computational time and deviation from the minimum objective function. For example, in some large problems, the objective function values obtained by the Lingo 8.0 software have 20% deviation from their minimum. Therefore, to solve such a hard problem, a meta-heuristic method is required as future research.
æèíîçæŶƬūæƵŹŚưƃ ŶǀƫƺţŢƿźƿŶƯƹƖƿŚƴƇƾſŶƴƸƯƾƬƬưƫřƲǀŝƶƿźƄƳ’

ƹƾƫřƺţƶŝƶŤƀŝřƹƽŻŚſƵŵŚƯōƱŚƯŻŚŝĥŚŤƳƺƯƾƷŚĭŹŚĩƱŚƿźūƽŶƴŞƳŚƯŻ
ƪƤƳƹƪưůƱŚƯŻ
ƱŚƿŵƺŞƘƯƲưſŚƿƹƾưţŚůřŹŚſƭŶƤƯƾƬĩƺţŚƋŹ˺ŵřĦƳƮǀƷřźŝřƶƫřŶƘſ

ííëççƩƺƇƹŲƿŹŚţ
ííæçæçŜƿƺƈţŲƿŹŚţ
[email protected] kiau.ac.irũźĩũźƧŶůřƹƾƯLjſřŵřŻōƵŚĮƄƳřŵƖƿŚƴƇƾſŶƴƸƯƵƹźĭŹŚƿŵŚŤſřŵřĦƳƮǀƷřźŝřƶƫřŶƘſźŤƧŵ [email protected] ut.ac.irƱřźƸţƱřźƸţƵŚĮƄƳřŵƾƴƟƽŚƷƵŶƨƄƳřŵžƿŵźěƖƿŚƴƇƾſŶƴƸƯƵƹźĭŵŚŤſřƭŶƤƯƾƬƧƺţŚƋŹźŤƧŵ
[email protected] gmail.com ƲƿƹżƣƲƿƹżƣŶůřƹƾƯLjſřŵřŻōƵŚĮƄƳřŵƖƿŚƴƇƾſŶƴƸƯŶƃŹřƾſŚƴƃŹŚƧƶŤųƺƯōƂƳřŵƾưţŚůřŹŚſ [email protected] sina.kntu.ac.irƱřźƸţƾſƺƏƲƿŶƫřźǀƈƳƶūřƺųƵŚĮƄƳřŵƖƿŚƴƇƾſŶƴƸƯŶƃŹřƾſŚƴƃŹŚƧƶŤųƺƯōƂƳřŵƱŚƿŵƺŞƘƯƲưſŚƿ
ƱŚƿŵƺŞƘƯƲưſŚƿƹƾưţŚůřŹŚſƭŶƤƯƾƬĩƺţŚƋŹŵřĦƳƮǀƷřźŝřƶƫřŶƘſƽŻŚſƵŵŚƯōƱŚƯŻŚŝĥŚŤƳƺƯƾƷŚĭŹŚĩƱŚƿźūƽŶƴŞƳŚƯŻæë

ƵŶǀĪģƽŶǀƬĩšŚưƬĩ

ƎſƺŤƯƽŻŚſƶƴǀưĩƝŶƷƹŵŚŝƽřƶƬůźƯƶſĥŚŤƳƺƯƾƷŚĭŹŚĩƱŚƿźūƽŶƴŞƳŚƯŻƶƫŐƀƯƶƫŚƤƯƲƿřŹŵĥŚŤƳƺƯƾƷŚĭŹŚĩƱŚƿźūƶƫŐƀƯ
ƽŚƷƮŤƀǀſŻřƾƫŶƯƶƫŐƀƯƲƿřŵƺƃƾƯƾſŹźŝŚƷŹŚĩŵźĩźƿŵƱŚƯŻƎſƺŤƯƹŚƷŹŚĩƭŚưţřƱŚƯŻŹŚĩƱŚƿźūƱŚƯŻƎſƺŤƯ
žĜſŶƳƺƃƾƯƭŚŬƳřƪƤŤƀƯƹƱŚƯżưƷŹƺƏƶŝƾţƹŚƠŤƯƽŶǀƫƺţšŚǀƬưƗƱōŹŵƶĩŢſřƽŶǀƫƺţ ŵźĩźƿŵƱŚƯŻƎſƺŤƯ ƲƿřŹŵŶƳƺƃƾƯƪƤŤƴƯƾƿŚƸƳšŚǀƬưƗƽřźŝĥŚŤƳƺƯƶƬůźƯƶŝƹƵŶƃƽŹƹōƖưūƽŶǀƫƺţšŚƘƐƣ ƾƫřƺţƶŝƶŤƀŝřƹƽŻŚſƵŵŚƯōƱŚƯŻ
1268732040128Downloaded from ijiepm.iust.ac.ir at 16:19 IRST on Saturday November 4th 2017

Downloaded from ijiepm.iust.ac.ir at 16:19 IRST on Saturday November 4th 2017

ƢǀƣŵƹƪƯŚĩƁŹŚưƃƪůƽŚƷƁƹŹ ƪƤƳƹƪưůƱŚƯŻƹƾƫřƺţƶŝƶŤƀŝřƹƽŻŚſƵŵŚƯōƱŚƯŻƲŤƟźĭźƔƳŹŵŚŝŢſřƵŶƃƾƘſƩŶƯ ƭŚưţřƱŚƯŻƽřźŝƲǀƿŚěŶůĨƿžĜſŵƺƃĨƿŵżƳƾƘƣřƹƎǀŰƯƶŝƵŶƃƾůřźƏƩŶƯšŚƘƐƣ ŹŵƾƟŵŚƈţšŹƺƇƶŝŚƷŹŚĩƪƿƺŰţŶƗƺƯƶƳƺưƳƽŚƷƶƫŚƀƯƽřźŝƶƯřŵřŹŵŵƺƃƾƯƶŗřŹřŚƷŹŚĩƶǀƬĩ íƺĮƴǀƫƽŻŚſƶƴǀƸŝŹřżƟřƭźƳ ŻřƽŵŚƸƴƄǀěƩŶƯƾŬƴſŹŚŞŤƗřƽřźŝŶƳƺƃƾƯŶǀƫƺţƵŶƃƲǀǀƘţƵŻŚŝ ŵƺƃƾƯƵŵŚƠŤſřŶƿŵźĭƾƀƿƺƳƶƯŚƳźŝ MATLABŹřżƟřƭźƳƎǀŰƯŹŵƶĩƪƯŚĩƁŹŚưƃƁƹŹƹ ƽŚƷƶƫŚƀƯŹŵƶĩŶƷŵƾƯƱŚƄƳƪƯŚĩƁŹŚưƃƹ íƺĮƴǀƫ ƎſƺţƪůŻřƵŶƯōŢſŶŝŪƿŚŤƳƶƀƿŚƤƯ ƝŶƷƖŝŚţŹřŶƤƯƝřźŰƳřƹƱŚƯŻźƔƳŻříƺĮƴǀƫƎſƺţƪůn>ínŚƷŹŚĩŵřŶƘţźŤĭŹżŝŵŚƘŝřŚŝ ƽŚƷƶƫŚƀƯŻřƾƌƘŝŹŵƶĩƽŹƺƏƶŝŢſřźţŶƯōŹŚĩŚƳƪƯŚĩƁŹŚưƃƁƹŹŻřƾƬĩƶƴǀƸŝŹřŶƤƯŻř ƱŚƄƳƝřźŰƳřçåƪƯŚĩƁŹŚưƃƁƹŹƶŝŢŞƀƳíƺĮƴǀƫŻřƵŶƯōŢſŵƶŝƝŶƷƖŝŚţŹřŶƤƯīŹżŝ
ƝŶƷƖŝŚţŹřŶƤƯŹŵƝřźŰƳřƱŵźĩƮĩƹƪůƱŚƯŻƂƷŚĩƽřźŝŵƺƃƾƯŵŚƸƴƄǀěƲƿřźŝŚƴŝŶƷŵƾƯ
ŵƺưƳƵŵŚƠŤſřƽŹŚĪŤŝřřźƟƽŚƷƮŤƿŹƺĮƫřŻřƱřƺţƾƯ

ƉźƟƲƿřƶĩŢſřżǀģŚƳƭƹŵƶƬůźƯƶŝƩƹřƶƬůźƯŻřƵŶƃ ƾƷŚĭŹŚĩƱŚƿźūƪŗŚƀƯŻřƶĩƾƳŚƯŻƅƺƈųƶŝŢſřŜſŚƴƯŚƳ ŶƴģŚŝƽŶǀƫƺţƽŚƷƮŤƀǀſƽŻŚſƶǀŞƃƽřźŝƽřƶƬůźƯƹŵƽĥŚŤƳƺƯ
ŵƺƃƵŵŚƠŤſřĥŚŤƳƺƯƶƳŚųŹŚĩŶůřƹĨƿƹƶƳŚųŹŚĩƾŤƘƴƇŶůřƹ ŵŶƘŤƯ šŚŬƳŚųŹŚĩ Żř ƾƬƇř ƽŚƷĥŚŤƳƺƯ źƿŻ ŚƷƮŤƀǀſ Ʋƿř Źŵ ĥŚŤƳƺƯƶƳŚųŹŚĩƶŝƾƿŚƸƳƩƺƈŰƯŶǀƫƺţƽřźŝƹŶƳƺƃƾƯƽŹƹōƖưū ƽŹƹōƖưūƪƯŚƃƶĩƾƳŚǀƯšŚǀƬưƗĨƿƶŬǀŤƳŹŵŶƳƺƃƾƯƪƤŤƴƯ ƲƿřƽřźŝƵŶƃƝźƇƱŚƯŻƱřżǀƯƹŵźǀĭšŹƺƇŶƿŚŝŢſřƩŚƤŤƳřƹ ƾƳŚǀƯšŚǀƬưƗƶŝŻŚǀƳŢƃŚĮƳřƵŶƿŵŚƳƱřƺţƾưƳřŹƾƳŚǀƯšŚǀƬưƗ ƽŶǀƫƺţƽŚƷƮŤƀǀſŹŵƵŵŚƠŤſřŵŹƺƯƽŚƷƪƯŚůƶƬǀſƹƶŝŜƬƛř
ƱŚƿŚěŌżū mƽŹƹōƖưūƶƠǀƓƹƪƯŚůŵƺƃƾƯƝźƏźŝźƿŸěƝŚƐƘƳř
ƽŹřŸĭŹŚŝƹƪưůžĜſƹƩƹřƶƬůźƯŹŵŹŚĩźƷƶŝƍƺŝźƯƶŤƟŚƿ
ŵŹřŵƵŶƸƗƶŝřŹĥŚŤƳƺƯƲǀƃŚƯƽƹŹźŝŚƷƱō źºƔƳŹŵŚŝƽřƶƬůźƯƶſĥŚŤƳƺƯƾƷŚĭŹŚĩƱŚƿźūƶƫŐƀƯƶƫŚƤƯƲƿřŹŵ ƭƹŵƶºƬůźƯŜºƫŚƣŹŵƶĩŹŚĩƪƤƳƹƪưůƹƽŹƹōƖưūƱŚƯŻƲŤƟźĭ
ƽřźºŝƾƫřƺºţƶºŝƶŤƀºŝřƹƽŻŚſƵŵŚƯōƱŚƯŻżǀƳƹŢſřƵŶƃƵŶƳŚŬƴĭ
ƶºĩŢºſřƽŵŹřƺƯƶƬưūŻřƩƹřƶƬůźƯƪƤŤƀƯƹƽŻřƺƯƽŚƷƲǀƃŚƯ
ŻřƶƫŐƀƯƶŬǀŤƳŹŵŵƺƃƾƯƽŶƴŞƫƺƯźƟƶƫŚƤƯƲƿřŹŵƱōƾƋŚƿŹƩŶƯ ƹƽŻřƺºƯƲǀºƃŚƯmƩƹřƶºƬůźƯŢºſřƵŶºƃƪǀĪƄºţƶºƬůźƯƶſ ŶƴƫƺƜƄƯŚƷŹŚĩƶŝƍƺŝźƯƽŚƷšŚǀƬưƗƹšŚƘƐƣŶǀƫƺţƶŝƶĩƪƤŤƀƯ
ƶƬůźƯƹŶƃŚŝƾƯƵŶƃŶǀƫƺţšŚƘƐƣƪƤƳƹƪưůƶƬůźƯƭƹŵƶƬůźƯ
ŢſřšŚƘƐƣĥŚŤƳƺƯƶƬůźƯƭƺſ
šŚºǀŝŵřŹƹźºƯƶºŝƭƹŵƂºŴŝŹŵŢſřźƿŻŭźƃƶŝƶƫŚƤƯƲƿřŹŚŤųŚſ ŻřźºƔƳŵŹƺºƯƶƫŐƀºƯƪºƯŚĩƾƟźƘƯƶŝƭƺſƂŴŝŵƺƃƾƯƶŤųřŵźě ƩŶºƯƾƟźƘƯƹƝřŶƷřŚƷŢƿŵƹŶŰƯƹšŚǀƋźƟƶƫŐƀƯƞƿźƘţƶƬưū ƶƯŶƤƯæ
ƱōŹŵƶĩŢſřƾŞǀĩźţƽŶǀƫƺţƮŤƀǀſĨƿĥŚŤƳƺƯƾƷŚĭŹŚĩƱŚƿźū ŶƳƺºƃƾƯƭŚŬƳřƱŚƯżưƷƹƪƤŤƀƯŹƺƏƶŝƾţƹŚƠŤƯƽŶǀƫƺţšŚǀƬưƗ ƪºƤŤƴƯĥŚºŤƳƺƯƎºųƶºŝƹƵŶºƃƽŹƹōƖưūƽŶǀƫƺţšŚƘƐƣžĜſ ƽŶǀƫƺţƍƺƐųƎſƺţšŚƘƐƣŻřƽřƶƗƺưŬƯƶƫŚƀƯƲƿřŹŵŶƳƺƃƾƯ
ƩƺƈºŰƯƶºŝĥŚºŤƳƺƯƶƬůźƯƎſƺţŚƸŤƳřŹŵƹŶƳƺƃƾƯŶǀƫƺţƪƤŤƀƯ
ƽŶºǀƫƺţƽŚºƷƮŤƀºǀſŻřƕƺºƳƲºƿřŶºƳŵźĭƾºƯƪƿŶŞţźƔƳŵŹƺƯ
ŹŚƄºƟƶºŝƾƿƺºĭŲºſŚěƽřźŝƾƬůƵřŹŵƺųƶŝƺƳƶŝŶƴƳřƺţƾƯƽĥŚŤƳƺƯ ƽřźºŝŻŚºǀƳƹƾƳŚƸūŢŝŚƣŹŶƴƃŚŝƕƺƴŤƯšLJƺƈŰƯŶǀƫƺţƽřźŝŹřŻŚŝ ŚºţŶƷŵƾƯơƺſƾŤưſƶŝřŹšŚŬƳŚųŹŚĩƽŶǀƫƺţƽŚƷƶƴƿżƷƩźŤƴĩ ƹšŚººƘƐƣŜººǀĩźţŚººŝƶººĩŶººƴƴĩƾººůřźƏƽŹƺººƏřŹšLJƺƈººŰƯ ŶºǀƫƺţƽźţƕƺƴŤƯšLJƺƈŰƯŶƴƳřƺŤŝŵŶƘŤƯƹƱƺĭŚƳƺĭƽŚƷĥŚŤƳƺƯźƿŻ ŻřŶƃŚŝƾƯŚƷŹŚŤųŚſƕƺƳƲƿřŶƿřƺƟƲƿźŤĭŹżŝŻřƾĪƿźƯřƲƿřŶƴƿŚưƳ ƱŚºƿźūŶºƴƳŚƯƽŶºǀƫƺţƽŚºƷƮŤƀºǀſƕƺºƳƲºƿřƽŶºƴŞƳŚƯŻƵŚĭŶƿŵ ƲŤƟźºĭźƔƳŹŵŚŝŶƳƺƃƾƯƽŻŚſƩŶƯƽřƶƬůźƯƹŵĥŚŤƳƺƯƾƷŚĭŹŚĩ ŚºŝĥŚŤƳƺƯƶƬůźƯƶŝŶǀƫƺţƶƬůźƯŻřšŚƘƐƣƪưůƹƽŹƹōƖưūƱŚƯŻ ƶºŝƹŹƽřƶƬůźƯƹŵĥŚŤƳƺƯƾƷŚĭŹŚĩƱŚƿźūƶƫŐƀƯŻřƽźţƾƘƣřƹƩŶƯ ƲǀºŝřżºŬƯƽřƶƬůźƯŜƫŚƣŹŵřŹƉźƟƲƿřƱřƺţƾƯŶƃƮǀƷřƺųƹŹ
ƶŝřŹƩŶƯƱřƺţƾƯŜǀţźţƲƿŶŝŶƳŚŬƴĭĥŚŤƳƺƯƶƬůźƯƹŶǀƫƺţƶƬůźƯ
ŶƃƹŹƶŝƹŹƽřƶƬůźƯƶſƩŶƯĨƿŚŝƹŵźĩĨƿŵżƳŢǀƘƣřƹ ŻřƶŤƟŚƿƮǀưƘţŢƫŚůƽřƶƬůźƯƶſĥŚŤƳƺƯƾƷŚĭŹŚĩƱŚƿźūƶƫŐƀƯ
ƱŚƿźūƪŗŚƀƯŹŵŢſřƽřƶƬůźƯƹŵƽĥŚŤƳƺƯƾƷŚĭŹŚĩƱŚƿźūƶƫŐƀƯ mŻřŹŚĩźƷƶĩŢſřƲƿřźŝƉźƟƽřƶƬůźƯƹŵĥŚŤƳƺƯƾƷŚĭŹŚĩ ŶǀƫƺţƪƤŤƀƯƽŻřƺƯƲǀƃŚƯ mƽƹŹƶĩŢſřƵŶƃƪǀĪƄţƶƘƐƣ
ƪǀưĪţŌżū mƪưůƹƽŹƹōƖưūƽřźŝŻŚǀƳŵŹƺƯƱŚƯŻƹžŶƳƺƃƾƯ
æìƱŚƿŵƺŞƘƯƲưſŚƿƹƾưţŚůřŹŚſƭŶƤƯƾƬĩƺţŚƋŹŵřĦƳƮǀƷřźŝřƶƫřŶƘſƽŻŚſƵŵŚƯōƱŚƯŻŚŝĥŚŤƳƺƯƾƷŚĭŹŚĩƱŚƿźūƽŶƴŞƳŚƯŻ

ĥŚŤƳƺƯƽřƶƬůźƯƶſƾƷŚĭŹŚĩƱŚƿźūƽŶƴŞƳŚƯŻƶƫŐƀƯè
ƶƫŚƀƯƞƿźƘţèæ ƶ ºƗƺưŬƯŻřƽřƵźººǀŬƳŻƪƯŚººƃ J j , j 1,2,…,n ŹŚ ºĩź ºƷ
Oi, j šŚºǀƬưƗŶƃŚŝƾƯ ({O1, j,…..,Om, j},OT, j,OA, j ) šŚǀƬưƗ Pi, j ŶƴƯŻŚǀƳƹŵƺƃƭŚŬƳřMi,i 1,2,…,m ƲǀƃŚƯƽƹŹźŝŶƿŚŝ ŚºƸƴţƱŚºƯŻŶºůřƹŹŵŶƳřƺţƾƯ M i ƲǀƃŚƯŶƴƃŚŝƾƯƾƳŚƯŻŶůřƹ ƽƹŹźºŝOT, j ƩŚºƤŤƳřƹƽŹƹōƖºưūƪºưƗŶºƷŵƭŚŬƳřřŹŹŚĩĨƿ
Ʃƺ Əƶ ŝƾƳŚ ƯŻŶ ůřƹPTj ƹŵƺ ƃƾ ƯƭŚ ŬƳř MT Ʋǀ ƃŚƯ
ŵƺƃƾƯƭŚŬƳřM A ƲǀƃŚƯƽƹŹźŝOA, j ĥŚŤƳƺƯƪưƗŶƯŚŬƳřƾƯ
ŶƯŚŬƳřƾƯƩƺƏƶŝƾƳŚƯŻŶůřƹPAj ƹ ,k 1,2,…,m i  k k ƹiŹŚºººººĩźºººººƷƽřźºººººŝ
ŶƴƳřƺţƾƯ j 1,2,…,nOk, j ƹ Oi, j šŚǀƬưƗi 1,2,…,m ŵƺƃƾƯŻŚƛōƾƳŚƯŻŚƸƴţOT, j ƪưƗŶƳƺƃƭŚŬƳřƱŚƯżưƷšŹƺƇƶŝ
ƹŶƴſźŝƭŚưţřƶŝO1, j ,…..,Om, j ƱŚƯżưƷƽŚƷšŚǀƬưƗƭŚưţƶĩ ƶƬǀºſƹŵƺºƃŻŚºƛōŶºƳřƺţƾƯOT, j ƪưƗƭŚưţřŻřŶƘŝOA, j ƪưƗ
řŹŹŚĩĨƿŌřżūřƭŚưţŢƿŚƸƳŹŵŶƳřƺţƾƯ MT ƩŚƤŤƳřƹƽŹƹōƖưū ŶƳřƺţƾƯ M A ĥŚŤƳƺƯƲǀƃŚƯƶŝŚƄƯŹƺƏƶŝŶƴĩŚŬŝŚūƱŚƯŻĨƿŹŵ
ƂƿŚºưƳæƪĪºƃŶºƿŚưƳĥŚºŤƳƺƯƱŚƯŻĨƿŹŵřŹŹŚĩĨƿŌřżūřƭŚưţ ŢſřźƔƳŵŹƺƯƩŶƯŻřƽřƵŵŚſ
J1 J2 J3
M1
ƩƹřƶƬůźƯ
J1 J2 J3
ƶƬůźƯ
ƶƬůźƯ
J1 J2 J3
J1 J2 J3
Mm
ƭƹŵ
MT
ƭƺſ
MA

ŶǀƫƺţŶƴƿōźƟŻřĨǀţŚưƃƂƿŚưƳæƪĪƃ
ƝřŶƷřèç
ŚºƷŹŚĩƭŚºưţřƱŚºƯŻƎſƺŤƯƽŻŚſƶƴǀưĩŻřŶƴţŹŚŞƗƶƫŐƀƯƝřŶƷř

T ŚƷŹŚĩŵźĩźƿŵƱŚƯŻƎſƺŤƯƹC
ŚƷŢƿŵƹŶŰƯƹšŚƋƹźƠƯèè
ƾºƯźƿŻŵŹřƺƯƵŶƃƶŤƟźĭźƔƳŹŵƩŶƯƽŚƷŢƿŵƹŶŰƯƹšŚƋƹźƠƯ
ŶƃŚŝ
ŶƴƃŚŝƾƯŽźŤſŵŹŵƽżƿŹƶƯŚƳźŝƢƟřƕƹźƃŹŵŚƷƲǀƃŚƯ 
ŶƴƃŚŝƾƯŽźŤſŵŹŵƽżƿŹƶƯŚƳźŝƢƟřƕƹźƃŹŵŚƷŹŚĩƶưƷ 
ƶºĩƾºƴƘƯƲƿŶŝŶƃŚŝƾưƳŻŚŬƯŚƷšŚǀƬưƗŹŵƾŤƀĪƃĢǀƷ
ŶſźŝƭŚưţřƶŝƶƠƣƹƱƹŶŝŶƿŚŝƵŶƃƕƹźƃšŚǀƬưƗŻřĨƿźƷ 
ŵŹřŶƳŵƺūƹƽŹŚĩƭŚŬƳřƽřźŝƾŤƿƺƫƹřĢǀƷ 
ƲǀƿŚºěŶůƶŞſŚŰƯŮƿźƄţƶŝƭŹŚƸģƂŴŝŹŵŵŻřŵźěƾƯƽŵŚƸƴƄǀě
1268732040128Downloaded from ijiepm.iust.ac.ir at 16:19 IRST on Saturday November 4th 2017

Downloaded from ijiepm.iust.ac.ir at 16:19 IRST on Saturday November 4th 2017

ƵŵŚƠŤºſřŚŝƮŬƴěƂŴŝŹŵŵƺƃƾƯƶŤųřŵźěƶƫŐƀƯƽřźŝƽŵŚƸƴƄǀě
ƪºůĨºģƺĩƵŻřŶºƳřŹŵƵŶºƃŶºǀƫƺţƪŗŚƀºƯíƺºĮƴǀƫŹřżºƟřƭźƳŻř
ŵƺƃƾƯƱŚǀŝƽźǀĭƶŬǀŤƳżǀƳƮƄƃƂŴŝŹŵŶƳƺƃƾƯ

ƕƺƋƺƯšŚǀŝŵřŹƹźƯç
ƹŵĥŚºŤƳƺƯƾƷŚºĭŹŚĩƱŚºƿźūƶƫŐƀºƯƶºƘƫŚƐƯƶŝ[æ]ƱřŹŚĪưƷƹƾƫ
ŶºƴŤųřŵźěƩƹřƶºƬůźƯŹŵƲǀºƃŚƯçƲŤƟźºĭźºƔƳŹŵŚºŝƽřƶƬůźƯ ƶºſƾƷŚĭŹŚĩƱŚƿźūƽŶƴŞƳŚƯŻƶƫŐƀƯ[ç]žǀƀƿŹŚĜƿŚĩƹŽŚƯLJƺĩ ŹŵŚƷŹŚĩƭŚưţřƱŚƯŻźŨĩřŶůƽŻŚſƶƴǀưĩƝŶƷŚŝřŹĥŚŤƳƺƯƽřƶƬůźƯ ƽŹŚºĪŤŝřƽŚºƷƮŤƿŹƺĮƫřƽřźŝŢƫŚůƲƿźţŶŝŢŞƀƳŶůƹŶƴŤƟźĭźƔƳ ƪºǀƬŰţŵŹƺºƯřŹŢºſřƵŶƃƶŤƟźĭźƔƳŹŵƶƫŐƀƯƽřźŝƶĩƽŵŶƘŤƯ ƽřƶƬůźƯƹŵƽŶƴŞƳŚƯŻƶƫŐƀƯ[è]ƱřŹŚĪưƷƹƱŚěŚĩŻƺţŶƳřƵŵřŵŹřźƣ ŹŵƱŚººƯŻƱƹŻƺººƯƕƺººưŬƯŵźººĪƬưƗŹŚººǀƘƯŚººŝŹŚººŝƲººƿřřŹĥŚººŤƳƺƯ ƽŚºƷƶºƯŚƳźŝƶºĩŶƳŵřŵƱŚƄƳƹŶƴŤƟźĭźƔƳŹŵŚƷŹŚĩŢųŚſƱŚƿźū ƵŶºƃƱŚǀŝƝŶƷŚŝƶƫŐƀƯƽřźŝƶƬůźƯźƷŹŵÎƾŤƄĮƿŚūƽŶƴŞƳŚƯŻ ƶºŗřŹřƱŚºƃƽŵŚƸƴƄǀěƶƫŐƀƯƽřźŝƲǀƿŚěŶůĨƿżǀƳƹŶƳŹřŵƾĭźǀģ ŚºŝřŹ[è]ƱřŹŚĪưƷƹƱŚěŚĩŻƺţƶƫŐƀƯ[é]ƽŵŹƹĽřƹƽżƳLJřŶƳŵźĩ ŚºƷƱōŶºƳŵźĩƽŶºƴŞƳŚƯŻŹŚºĩnƭŚŬƳřƱŚƯŻƪĩƽŻŚſƶƴǀưĩƝŶƷ ƕƺºƴưƯƽƺŬŤƀºūƹƕƺƴưƯƽƺŬŤƀūÏŶƿźŞţƽŻŚſƶǀŞƃƮŤƿŹƺĮƫř ƽżºƳLJřƹƽŵŹƹĽřŶºƳŵźĩŵŚƸƴƄºǀěƾºƬĩŵŹřƺºƯƽřźŝřŹÐƾŞǀĩźţ ƶŤƟŚƿƖƿŻƺţƽŚƷƮŤƀǀſŹŵřŹƾƷŚĭŹŚĩƱŚƿźūƽŶƴŞƳŚƯŻƪŗŚƀƯ[ê] źŨĩřŶºůƽŻŚºſƶºƴǀưĩƾºſŹźŝŵŹƺƯƝŶƷŶƳŵźŝŹŚĩƶŝƵŵřŵƵŚĮƿŚě ŶºƴģƶƫŐƀƯƲƿřƽřźŝƲǀƴĤưƷŶƃŚŝƾƯCmaxŚƷŹŚĩƭŚưţřƱŚƯŻ
ƹÑƵƺºŞƳřšřŹŷƽŻŚºſƶºƴǀƸŝƮŤƿŹƺºĮƫřƹŵƵřźºưƷƶºŝƾĭźǀģƶƐŝřŹ ƽŵŹƹĽřƹƽżºƳLJřŶºƳŵźĩŵŚƸƴƄǀěƱōƪůƽřźŝƕƺƴưƯƽƺŬŤƀū ƽřƶƬůźƯƹŵĥŚŤƳƺƯƾƷŚĭŹŚĩƱŚƿźūƽŶƴŞƳŚƯŻƶƫŐƀƯƾſŹźŝƶŝ[ë] ŚºŝŚºƷŹŚĩƭŚŬƳřƾƫřƺţŻřƪƤŤƀƯƽŻŚſƵŵŚƯōƱŚƯŻƲŤƟźĭźƔƳŹŵŚŝ ĨºƿƹŶºƳřƶºŤųřŵźěŵźºĩźƿŵƱŚºƯŻƲƿźŤƄºǀŝƽŻŚºſƶƴǀưĩƝŶƷ ƪºůƽřźºŝřŹÒƾƣŚºŞƐƳřŵƺºųƾƬǀƀƳřźƠƿŵƾƬƯŚĪţƽŹŚĪŤŝřƮŤƿŹƺĮƫř ƪŗŚƀºƯƶºƴǀƯŻŹŵƶºŤƟźĭšŹƺƇšŚƤǀƤŰţŻřŶƳŵřŵŵŚƸƴƄǀěƶƫŐƀƯ ƾºƯƝŶƷƖŝŚţĨƿŻřƂǀŝŚŝƽřƶƬůźƯƹŵĥŚŤƳƺƯƾƷŚĭŹŚĭƱŚƿźū ƱŚºƯŻźŨĩřŶºůƽŚºƷŹŚǀƘƯŚŝ[ì]ƽżƳLJřƹƽŵŹƹĽřƢǀƤŰţƶŝƱřƺţ ƁƹŹŻřƱōŹŵƶĩŵźĩƵŹŚƃřŚƷŹŚĩƭŚưţřƱŚƯŻƲǀĮƳŚǀƯƹŚƷŹŚĩƭŚưţř ƵŵŚƠŤºſřƩŶºƯƪºůŹŵƝřŶƷřŜǀĩźţƝŶƷƖŝŚţƹŵƾƳŻƹƕƺưŬƯ ƮŤƿŹƺºĮƫřŶƿźŞţƽŻŚſƶǀŞƃƽŹŚĪŤŝřƮŤƿŹƺĮƫřƶſŚƷƱōŢſřƵŶƃ
řŹƾƣŚºŞƐƳřŵƺºųƾƬǀƀƳřźƠƿŵƾƬƯŚĪţƽŹŚĪŤŝřƮŤƿŹƺĮƫřƹÓƱŚĮģŹƺƯ
ŶƳřƵŵźĩŵŚƸƴƄǀěƶƫŐƀƯƪůƽřźŝ

˺- Permutation
˻- Simulated Annealing (SA)
˼- Hybrid Tabu Search (HTS)
˺- Particle Swarm Optimization (PSO)
˻- Self-Adaptive Differential Evolution (SDE)
˼- Ant Colony Optimization (ACO)
ƱŚƿŵƺŞƘƯƲưſŚƿƹƾưţŚůřŹŚſƭŶƤƯƾƬĩƺţŚƋŹŵřĦƳƮǀƷřźŝřƶƫřŶƘſƽŻŚſƵŵŚƯōƱŚƯŻŚŝĥŚŤƳƺƯƾƷŚĭŹŚĩƱŚƿźūƽŶƴŞƳŚƯŻæí

ƶºƬůźƯĥŚºŤƳƺƯƶºƬůźƯŹŵƭři ŢǀƘƣƺƯŹŵŹŚĩƭŚưţřƱŚƯŻC[i]
ƭƺſ Źŵƭři ŢºǀƘƣƺƯŹŵŹŚºĩƲǀºƫƹřƕƹźºƃŚºţƽŹŚĪǀŝƱŚƯŻ2[i]
ƭƹŵƶƬůźƯ
ƭƺſƶƬůźƯŹŵƭři ŢǀƘƣƺƯŹŵŹŚĩƕƹźƃŚţƽŹŚĪǀŝƱŚƯŻ3[i]
ƭři ŢǀƘƣƺƯŹŵŹŚĩƶŝƍƺŝźƯŵźĩźƿŵƱřżǀƯT[i]
ƹC

ŚºƷŹŚĩƭŚºưţřƱŚºƯŻƎſƺŤƯƝŶƷƖŝŚţƱŵŹƹōŢſŵƶŝƽřźŝ ŻřĨƿźƷƪǀưĪţƱŚƯŻƶŞſŚŰƯŶƴƯŻŚǀƳT

ŵźĩźƿŵƱŚƯŻƎſƺŤƯ
źºƯřƲƿřƶŝƩƺƈůƽřźŝƶĩƮǀƃŚŝƾƯƭƺſĥŚŤƳƺƯƶƬůźƯŹŵŚƷŹŚĩ ŵŵźĭƾƯŵŚƸƴƄǀěźƿŻƁƹŹƹŵ
ƶ ĩƾƿŚ ūƱōŻřŚ ƷŹŚĩƪ ǀưĪţƱŚ ƯŻƶŞ ſŚŰƯƩƹřƁƹŹ
ŹŚºĩƭŚºưţřƱŚºƯŻƱřƺºţƾºƯæƶƐŝřŹƶŝƶūƺţŚŝŢſřCT[0]  0
ƹƪưůƶƬůźƯƽŚƸŤƳřŹŵřŹƾƫřƺţƭři ŢǀƘƣƺƯŹŵƶŤƟŚƿƆǀƈŴţ ŵŹƹōŢſŵźƿŻšŹƺƇƶŝƪƤƳ
i
CT[i]  max{ max { S[l1,l,k] t[l,k]} k1,….,m l1 æ
,CT[i1]} PT[i]i 1,…,n

ŹŚĩƭŚưţřƱŚƯŻƱřƺţƾƯæƶƐŝřŹƹC[0]  0 ƲŤƟźĭźƔƳŹŵŚŝ
ƶŝřŹĥŚŤƳƺƯƶƬůźƯŹŵƾƫřƺţƭři ŢǀƘƣƺƯŹŵƶŤƟŚƿƆǀƈŴţ ŵŹƹōŢſŵƶŝźƿŻšŹƺƇ
C[i]  max{CT[i] ,C[i1]} PA[i]
i  1,…, n ç

ĨºţĨţƽŹŚĪǀŝƱŚƯŻŚƷŹŚĩƪǀưĪţƱŚƯŻƶŞſŚŰƯƭƹŵƁƹŹ
ƹƪºưůƶƬůźƯŹŵźƔƳŵŹƺƯŹŚĩŚţƾƫřƺţƭři ŢǀƘƣƺƯŹŵƽŚƷŹŚĩ ŵŹƹōŢſŵƶŝè ƶƐŝřŹƎſƺţƱřƺţƾƯřŹƪƤƳ
ii1
1268732040128Downloaded from ijiepm.iust.ac.ir at 16:19 IRST on Saturday November 4th 2017

Downloaded from ijiepm.iust.ac.ir at 16:19 IRST on Saturday November 4th 2017

2[i]  kmax1,…,m{S[l1,l,k] t[l,k]}PT[l]
l1l1
i 1,…,n è

ŚºţƶºŤƟźĭŹřźƣƽŚƷŹŚĩƭŚưţŻřƵŶƯōŢſŵƶŝƽŹŚĪǀŝƱŚƯŻƲƿźŤƄǀŝ ŶƿōƾƯŢſŵƶŝéƶƐŝřŹƎſƺţƶĩŢſřźƔƳŶƯźƔƳŵŹƺƯŹŚĩ
i
2[i]  max{0,2[l]} i 1,…,n é
l1

ƶƬůźƯŹŵźƔƳŵŹƺƯŹŚĩŚţƶŤƟźĭŹřźƣƽŚƷŹŚĩĨţĨţƽŹŚĪǀŝƱŚƯŻ ŶƿōƾƯŢſŵƶŝêƶƐŝřŹƎſƺţĥŚŤƳƺƯ
ii1
3[i] 2[i]  PT[l]  ( PA[l])
l1l 1 i 1,…,n ê
ŶƃŚŝƾƯŢŝŚŧƹƾƘƐƣŚŤƀƿřƕƺƳŻřƶƫŐƀƯ 
ƁŻřŵźěŹŚĩĨƿƽƹŹźŝŶƳřƺţƾƯŚƸƴţƶƔŰƫźƷŹŵƲǀƃŚƯźƷ
ŶƷŵƭŚŬƳř 
ƲǀºƃŚƯƶģŚƷƲǀƃŚƯƭŚưţƽƹŹźŝŚƷŹŚĩƲŤƟźĭŹřźƣŜǀţźţ
ƭƺºſƹƭƹŵƶƬůźƯƽŚƷƲǀƃŚƯƶģƹƩƹřƶƬůźƯƽŻřƺƯƽŚƷ ŢſřƾŤƄĮƿŚūƽŶƴŞƳŚƯŻƕƺƳŻřƹŶƃŚŝƾƯƱŚƀĪƿ 
ƵŵŚºƯōƽŚºƷƱŚºƯŻƽřŹřŵƩƹřƶƬůźƯƽŻřƺƯƽŚƷƲǀƃŚƯƭŚưţ
ƮºƛŹƾºƬƗƶºĩŜǀţźţƲƿŶŝŶƴƃŚŝƾƯƾƫřƺţƶŝƶŤƀŝřƹƽŻŚſ
ƽŻŚºſƵŵŚºƯōƱŚºƯŻƲǀƃŚƯƽƹŹźŝŹŚĩƹŢǀƫŚƘƟƭŚŬƳřƱŚƯŻ ŵźǀĭŹřźƣźƔƳŶƯŶƿŚŝƾƬƘƟƹƾƬŞƣŹŚĩƶŝƶŤƀŝ 
ƱŚƀĪƿźǀƛƩƹřŶǀƫƺţƶƬůźƯŹŵŵƺūƺƯƽŻřƺƯƽŚƷƲǀƃŚƯ ŚƷƲǀƃŚƯƽřźŝƁŻřŵźěƹƽŻŚſƵŵŚƯōƽŚƷƱŚƯŻŶƴŤƀƷ ŢſřšƹŚƠŤƯ 
ŶǀſŹƱŚƿŚěƶŝƩƹřƶƬůźƯŹŵŹŚĩƽřżūřƶưƷŶǀƫƺţƶĩƾƳŚƯŻ
ƪƣřŶůŵƺƃƾƯƪƤŤƴƯƭƹŵƽƶƬůźƯƶŝƹƵŶƃƽŹƹōƖưū ƱŚƯŻźŨĩřŶůŚŝźŝřźŝƭƹŵƶƬůźƯŹŵźƔƳŵŹƺƯŹŚĩƕƹźƃƱŚƯŻ
ƶƬůźƯŹŵƽŻřƺƯƽŚƷƲǀƃŚƯƽƹŹźŝƱōƽřżūřƭŚưţƭŚưţř
ŶƃŚŝƾƯƩƹřƪŞƣ 
ƪưƗƶĩŵƺƃƾƯƕƹźƃƭƺſƶƬůźƯŹŵĥŚŤƳƺƯƪưƗƾƳŚƯŻ
ŶƃŚŝƵŶǀſŹƱŚƿŚěƶŝƭƹŵƶƬůźƯŹŵƩŚƤŤƳř 
ŶƃŚŝƾƯŵƺūƺƯƁŹŚƠſĨƿŚƸƴţŹŚĩźƷŻř 
ƽźǀĭƮǀưƈţƽŚƷźǀƜŤƯƹŚƷźŤƯřŹŚěèé
ŚƷźŤƯřŹŚě
ŶƳƺƃƽżƿŹƶƯŚƳźŝŶƿŚŝƶĩƾƿŚƷŹŚĩŵřŶƘţn
ƩƹřƶƬůźƯŹŵƪƤŤƀƯƱŚƯżưƷƽŚƷƲǀƃŚƯŵřŶƘţm
ŢǀƘƣƺƯŹŵŹŚĩŻřƭřk ƲǀƃŚƯƽƹŹƽŻŚſƵŵŚƯōƱŚƯŻS[i1,i,k] ƭři ŢǀƘƣƺƯŹŵŹŚĩƶŝƭři 1
źŝƾƫřƺţƩƹřŢǀƘƣƺƯŹŵŹŚĩƽřźŝƶǀƫƹřƽŻŚſƵŵŚƯōƱŚƯŻS[0,1,k]
ƩƹřƶƬůźƯŹŵƭřk ƲǀƃŚƯƽƹŹ
ƭřk ƲǀºƃŚƯƽƹŹźºŝƭři ŢǀƘƣƺƯŹŵŹŚĩŶƴƿōźƟƱŚƯŻt[i,k]
ƩƹřƶƬůźƯŹŵ
ŢºǀƘƣƺƯŹŵŹŚºĩƩŚºƤŤƳřƹƽŹƹōƖưūƽřźŝŻŚǀƳŵŹƺƯƱŚƯŻPT[i] ƭƹŵƶƬůźƯŹŵƩŚƤŤƳřĥŚŤƳƺƯƶƬůźƯƶŝƩƹřƶƬůźƯŻřƭři
ƭři ŢǀƘƣƺƯŹŵŹŚĩƭƺſƶƬůźƯĥŚŤƳƺƯƱŚƯŻPA[i]
ƭři ŢǀƘƣƺƯŹŵŹŚĩƪƿƺŰţŶƗƺƯd[i] ƭři ŢǀƘƣƺƯŹŵŹŚĩƪƿƺŰţŶƗƺƯŻřƝřźŰƳřL[i]
ŚƷźǀƜŤƯ
ƩŚºƤŤƳřƹƪƤƳƶƬůźƯŹŵƭři ŢǀƘƣƺƯŹŵŹŚĩƭŚưţřƱŚƯŻCT[i]
ƭƹŵƶƬůźƯ
æîƱŚƿŵƺŞƘƯƲưſŚƿƹƾưţŚůřŹŚſƭŶƤƯƾƬĩƺţŚƋŹŵřĦƳƮǀƷřźŝřƶƫřŶƘſƽŻŚſƵŵŚƯōƱŚƯŻŚŝĥŚŤƳƺƯƾƷŚĭŹŚĩƱŚƿźūƽŶƴŞƳŚƯŻ
ƱōƽŶƴŝƩƺƯźƟƹƽŵŚƸƴƄǀěƾƋŚƿŹ ƩŶƯƶŗřŹřèê
ŚŝƶŤŴǀƯōƾƐųźǀƛƽżƿŹƶƯŚƳźŝƾƋŚƿŹƩŶƯĨƿƂŴŝƲƿřŹŵ ƵŶƃƶŗřŹřźƔƳŵŹƺƯźƔƳŹŵƶƫŐƀƯƽřźŝINLP ÎŮǀŰƇŵřŶƗř
ƩŶƯƽźǀĭƮǀưƈţƽŚƷźǀƜŤƯƹŚƷźŤƯřŹŚěƾƟźƘƯƶŝřŶŤŝřŢſř
ŵƺƃƾƯƱŚǀŝƽŵŚƸƴƄǀěƾƋŚƿŹ
ƾƫřƺţŢǀƘƣƺƯžƿŶƳři
ŹŚĩƵŹŚưƃžƿŶƳř j
ƩƹřƶƬůźƯŹŵƲǀƃŚƯƵŹŚưƃžƿŶƳřk
ƭři ŢǀƘƣƺƯƶŝƭř j ŹŚĩźĭřŵƺŝŶƷřƺųæźŝřźŝx[i] j
ŢſřźƠƇźŝřźŝšŹƺƇƲƿřźǀƛŹŵŶŝŚƿƆǀƈŴţ
ŹŚĩƶŝƭř q ŹŚĩŻřƾƫřƺţƶŝƶŤƀŝřƹƽŻŚſƵŵŚƯōƱŚƯŻSq, j,k
ƩƹřƶƬůźƯŻřƭřk ƲǀƃŚƯƽƹŹƭř j
ƩƹřƶƬůźƯŹŵƭřk ƲǀƃŚƯƽƹŹƶǀƫƹřƽŻŚſƵŵŚƯōƱŚƯŻS0, j,k
ŵźǀĭŹřźƣƾƫřƺţƩƹřŢǀƘƣƺƯŹŵƭř j ŹŚĩƶĩƾţŹƺƇŹŵ
ŹŵŹŚĩƶŝƍƺŝźƯšŚǀƬưƗ mƶǀƬĩƪǀưĪţƱŚƯŻźŨĩřŶů y[i]
ƩƹřƶƬůźƯƾƫřƺţƭři ŢǀƘƣƺƯ
ŹŵŹŚĩŻřƭřk ƲǀƃŚƯƽƹŹšŚǀƬưƗƽŚƷƱŚƯŻƕƺưŬƯ A[i], j,k
Źŵƭř j ŹŚĩƶĩƾţŹƺƇŹŵƭři ŢǀƘƣƺƯŚţƩƹřŢǀƘƣƺƯ
ŶƃŚŝƶŤƟźĭŹřźƣƭři ŢǀƘƣƺƯ
ƭři ŢǀƘƣƺƯŹŵŹŚĩƶŝƍƺŝźƯƪƤƳƹƪưůƪưƗŻŚƛōƱŚƯŻZ[i]
ƭři ŢǀƘƣƺƯŹŵŹŚĩƶŝƍƺŝźƯĥŚŤƳƺƯƪưƗŻŚƛōƱŚƯŻw[i]
ƶƬůźƯŹŵƭřk ƲǀƃŚƯƽƹŹźŝ ƭř  j ŹŚĩŶƴƿōźƟƱŚƯŻt j,k
Ʃƹř
ƭƹŵƶƬůźƯƶŝƭř j ŹŚĩƩŚƤŤƳřƹƽŹƹōƖưūƽřźŝƭŻLJƱŚƯŻPTj
ƭƺſƶƬůźƯŹŵƭř j ŹŚĩĥŚŤƳƺƯƱŚƯŻPAj

min :Z  (n

C[i] )  (1)(n

T[i] ) æè
i1 ni1 n
s.t.

n
x[i] j 1 j æé
i1

n
x[i] j 1 i æê j1

n
A[i], j,k  x[i]j (tj,k  (x[i1]q  Sq, j,k))
q1,q j
næë
 A[i1],l,kj,k,i 2,3,…,n
l1,l j

˺-
Integer Non-Linear Programming
1268732040128Downloaded from ijiepm.iust.ac.ir at 16:19 IRST on Saturday November 4th 2017

Downloaded from ijiepm.iust.ac.ir at 16:19 IRST on Saturday November 4th 2017

ƭŚºưţŻřƵŶºƯōŢºſŵƶºŝƽŹŚºĪǀŝƱŚƯŻƲƿźŤƄǀŝéƶƐŝřŹŶƴƳŚưƷ
ƶƐŝřŹƎſƺţĥŚŤƳƺƯƶƬůźƯƽřźŝźƔƳŵŹƺƯŹŚĩŚţƶŤƟźĭŹřźƣƽŚƷŹŚĩ ŶƿōƾƯŢſŵƶŝë
i
3[i]  max{0,3[l]}i  1,…, n ë
l1
ƶŝƱřƺţƾƯŹŚĩźƷŻřƪŞƣƽŹŚĪǀŝƽŚƷƱŚƯŻƱŶƯōŢſŵƶŝŻřžě
ŢǀƘƣƺƯŹŵƶŤƟźĭŹřźƣŹŚĩƭŚưţřƱŚƯŻíƹìƎŝřƹŹĨưĩ
ŢſŵƶŝĥŚŤƳƺƯƹƪƤƳƹƪưůƶƬůźƯŹŵŜǀţźţƶŝřŹƾƫřƺţƭři
ŵŹƹō
i
CT[i] PT[l] 2[i] i  1,…, n ì
l1

i
C[i] PA[l] 3[i] i  1,…, n í
l1

T ŚƷŹŚĩŵźĩźƿŵƱŚƯŻƎſƺŤƯƝŶƷƖŝŚţƶŞſŚŰƯèéæ
ƶŤƟŚƿƆǀƈŴţƽŚƷŹŚĩƽřźŝƪƿƺŰţŶƗƺƯŹŵźǀųŚţƱŚƯŻîƶƐŝřŹ
ŶƴĩƾƯƶŞſŚŰƯřŹƭři ŢǀƘƣƺƯŹŵ
L[i]  C[i] d[i] i  1,…, n î
ŢǀƘƣƺƯŹŵƶŤƟŚƿƆǀƈŴţƽŚƷŹŚĩƽřźŝŵźĩźƿŵƱŚƯŻæå ƶƐŝřŹ
ŶƴĩƾƯƶŞſŚŰƯřŹƭři

T[i]  max{0,L[i]} i  1,…, n æå

ƶŞſŚŰƯææƶƐŝřŹƎſƺţT ŚƷŹŚĩŵźĩźƿŵƱŚƯŻƎſƺŤƯƹ ŵƺƃƾƯ
n

T[i]
312290-21230

T  i1 i  1,…, n ææ n
ŚƷŹŚĩ ƱŚƿźū Źŵ ƱŚƯŻ ƎſƺŤƯƝŶƷ ƖŝŚţ ƶŞſŚŰƯèéç

C
ƭři ŢǀƘƣƺƯŹŵƶŤƟŚƿƆǀƈŴţŹŚĩƭŚưţřƱŚƯŻƶŞſŚŰƯŻřžě
ŹŵƱŚƯŻƎſƺŤƯæç ƶƐŝřŹƎſƺţƱřƺţƾƯĥŚŤƳƺƯƶƬůźƯŹŵƾƫřƺţ ŵŹƹōŢſŵƶŝřŹŚƷŹŚĩƱŚƿźū
n

C[i]
310767-22707

C  i1 i  1,…, n æç n
ƱŚƿŵƺŞƘƯƲưſŚƿƹƾưţŚůřŹŚſƭŶƤƯƾƬĩƺţŚƋŹŵřĦƳƮǀƷřźŝřƶƫřŶƘſƽŻŚſƵŵŚƯōƱŚƯŻŚŝĥŚŤƳƺƯƾƷŚĭŹŚĩƱŚƿźūƽŶƴŞƳŚƯŻçå

ŢƿŵƹŶŰƯŶƃŚŝƾƯƭři ŢǀƘƣƺƯŹŵŹŚĩƽřźŝĥŚŤƳƺƯƪưƗŻŚƛō ƆǀƈŴţŹŚĩƶŝƍƺŝźƯŵźĩźƿŵƶŞſŚŰƯƵƺŰƳçëƹçê ƽŚƷ
ƱŚƄƳçìƶƐŝřŹŶƴƷŵƾƯƱŚƄƳřŹƾƫřƺţƭři ŢǀƘƣƺƯŹŵƶŤƟŚƿ ŢſřxijƮǀưƈţźǀƜŤƯƶŝĨƿƹźƠƇźƿŵŚƤƯƆǀƈŴţƵŶƴƷŵ
ƽřźŝƲǀƿŚěŶůƱŵŹƹōŢſŶŝƽřźŝƁƹŹĨƿƶŗřŹřé ƶƫŐƀƯ
ŹŵƾƟŵŚƈºţšŹƺºƇƶŝŚƷŹŚĩƪƿƺŰţŶƗƺƯƶƳƺưƳƪŗŚƀƯŶǀƫƺţƽřźŝ
ƶĩŵƺƃƾƯŶǀƫƺţ[í][LB(1T 

R),LB(1T 

R)]ƵŻŚŝ
22
ƭŚºưţřƶºŝŚºƷŹŚĩƭŚºưţƶºĩŢºſřƾƳŚºƯŻƵŶºƴƷŵƱŚƄƳLBƱōŹŵ ƭŚºưţřƱŚºƯŻƽřźºŝƲǀƿŚºěŶºůĨƿƱřƺƴƗƶŝLBľLJƺưƘƯŶƴſŹƾƯ ŹƺŤĩŚºƟƵŶƴƷŵƱŚƄƳTźŤƯřŹŚěŵƺƃƾƯƶŤƟźĭźƔƳŹŵŚƷŹŚĩƭŚŬƳř ƪºƿƺŰţƽŚƷŶºƗƺƯƵŻŚºŝƾŞƀºƳƩƺºƏRƶĩƾƫŚůŹŵŢſřŵźĩźƿŵ ŶºƗƺƯƵŻŚºŝƹƲǀƿŚºěŶůƱŵŹƹōŢſŵƶŝŮǀƋƺţƽřźŝ[ë]ŶƃŚŝƾƯ ƵŚĭŶºƿŵŻřŢſřƵŶƃƵŵŹƹōŶƴƿōźƟƲƿřƭŚŬƳřƪůřźƯźƿŻŹŵƪƿƺŰţ ƱŚºƯŻŜǀĩźţŚŝƵŶƃƶŗřŹřƶƫŐƀƯŹŚŤųŚſƹƅřƺųƾƋŚƿŹƾĭŶǀĤǀě
ŶºƷřƺųƾƣŚºŝƱŚƀºĪƿžƿźţŚƯĨƿŹŵƽŻŚſƵŵŚƯōƱŚƯŻƹƁŻřŵźě [î]ƮǀƯŚºƳƾºƯƵŶƃƮǀƔƴţžƿźţŚƯřŹƾŞǀĩźţžƿźţŚƯƲƿřƶĩŶƳŚƯ ŚºƷŹŚĩƁŻřŵźºěƱŚºƯŻƹƽŻŚſƵŵŚƯōƱŚƯŻŜǀĩźţŚŝƶĩƾƴƘƯƲƿŶŝ
ƵŶºƃƶºŗřŹřƶƫŐƀºƯŹŚŤųŚſƹƅřƺųƾĭŶǀĤǀěçìƶƐŝřŹƢŝŚƐƯ
ŵźĩŶƷřƺŴƳƽźǀǀƜţ APqjk  Sq, j,k t j,k i, j,k çì

ƭŚưţƽřźŝŶƿōƾƯŢſŵƶŝçìƶƐŝřŹƢƿźƏŻřƶĩƾŞǀĩźţžƿźţŚƯ
ƾƸŝŚƄºƯŵźºĪƿƹŹŵƺºƃƾƯƶŞſŚŰƯƩƹřƶƬůźƯƽŻřƺƯƽŚƷƲǀƃŚƯ ƹ j źƷƽřźŝŢſřƶŤƟźĭŹřźƣƵŵŚƠŤſřŵŹƺƯ[æå]ƺǀƿŹŶƴūƎſƺţ
ƽřźºŝƵŶºƃƮǀºƔƴţƁŻřŵźěƱŚƯŻƲƿźŤưĩšŹƺƇƶŝMAPjk k
ƶºƐŝřŹƢŝŚºƐƯƶĩŢſřƩƹřƶƬůźƯŹŵƭřk ƲǀƃŚƯƽƹŹźŝjŹŚĩ ŵƺƃƾƯƞƿźƘţçí

MAPjk  min{APqjk}q j j,k çí
q0,1,…n
n
SUMMAPk MAPjk k çî
j1

źºƷƽřźºŝŚºƷMAPjk ƖºưūŚŝçîƶƐŝřŹƢŝŚƐƯƱřƺţƾƯžĜſ řŹƁŻřŵźºěƱŚºƯŻƽŻŚſƵŵŚƯōƱŚƯŻƲĪưƯŶůƲƿźŤưĩƲǀƃŚƯ ƩƹřƶºƬůźƯŹŵŚºƷƲǀƃŚƯŻřĨƿźƷƽƹŹźŝŚƷŹŚĩŻřƾƫřƺţźƷƽřźŝ
1268732040128Downloaded from ijiepm.iust.ac.ir at 16:19 IRST on Saturday November 4th 2017

Downloaded from ijiepm.iust.ac.ir at 16:19 IRST on Saturday November 4th 2017

šŚºǀƬưƗŶºƿŚŝƭƹŵƶºƬůźƯŹŵŹŚºĩƕƹźºƃƽřźŝƱƺģŵŹƹōŢſŵƶŝ ŵƺƃƭŚưţƩƹřƶƬůźƯƽŻřƺƯƽŚƷƲǀƃŚƯƭŚưţƽƹŹźŝŚƷŹŚĩŻřĨƿźƷ ƵŶºƯōŢºſŵƶŝŶůƲƿźŤƄǀŝƶŬǀŤƳŹŵŶŝŚƿƵřŹŶƘŝƶƬůźƯƶŝŹŚĩŚţ ƽŚƷƲǀƃŚƯƭŚưţƲǀƿŚěŶůƱřƺƴƗƶŝƩƹřƶƬůźƯƽŚƷƲǀƃŚƯƭŚưţŻř A[i], j,k  y[i] i, j,k æì
y[i] Z[i] i æí

CT[i]  Z[i] n (x[i] j  PTj ) i æî
j1
CT[i1]  Z[i] i çå

CT[i]  w[i] i çæ
C[i]  w[i] n (x[i] j  PAj ) i çç
j1

C[i1] w[i] i çè

T[i]  C[i] n (x[i] j d[i]) i çé
j1

T[i]  0 i çê
xij {0,1} i, j çë

ƹŵŻřźƫŚĪſřŜǀĩźţŚŝƶƫŚƀƯƝŶƷƖŝŚţƵŶƴƷŵƱŚƄƳæèƶƐŝřŹ
ŵźĩźƿŵƱŚƯŻƎſƺŤƯƽŚƷŹŚĩƶǀƬĩƪǀưĪţƱŚƯŻƎſƺŤƯƝŶƷƖŝŚţ
ŶƃŚŝƾƯŚƷŹŚĩƶǀƬĩƽřźŝ
ŹŚĩźƷƶĩŶƴƷŵƾƯƱŚƄƳŜǀţźţƶŝæêƹæé ƽŚƷŢƿŵƹŶŰƯ ŢǀƘƣƺƯźƷƹŶƃŚŝƶŤƃřŵŹřźƣŶƳřƺţƾƯƾƫřƺţŻřŢǀƘƣƺƯĨƿŹŵŚƸƴţ
æìƹæëƎŝřƹŹŶƷŵƅŚƈŤųřŵƺųƶŝřŹŹŚĩĨƿŶƳřƺţƾƯŚƸƴţ
A[i], j,k ƹA[1],j,kƵŶƃƾƟźƘƯƽŚƷźǀƜŤƯƶŞſŚŰƯƵƺŰƳŜǀţźţƶŝ
ŶƴƷŵƾƯƱŚƄƳ A[i], j,k źǀƜŤƯƞƿźƘţƶŝƶūƺţŚŝřŹ
ƩƹřƶƬůźƯŹŵšŚǀƬưƗmƭŚưţřƱŚƯŻƵŶƴƷŵƱŚƄƳæíŢƿŵƹŶŰƯ ƶŝƍƺŝźƯæîŢƿŵƹŶŰƯŢſřƾƫřƺţƭři ŢǀƘƣƺƯŹŵŹŚĩƽřźŝ ƶƬůźƯŹŵƾƫřƺţƭři ŢǀƘƣƺƯŹŵŹŚĩšŚǀƬưƗmƶǀƬĩƭŚưţřƭƹżƫ çåŢƿŵƹŶŰƯŢſřƪƤƳƹƪưůƭƹŵƶƬůźƯŻŚƛōŻřƂǀěƩƹř
ƶƬůźƯŹŵƾƫřƺţŻřƭři ŢǀƘƣƺƯŹŵŹŚĩƭŚưţřƱŚƯŻƶŞſŚŰƯƵƺŰƳ
ŶƷŵƾƯƱŚƄƳřŹƪƤƳƹƪưů ŹŵŹŚĩƪưůƪưƗƭŚŬƳřƽřźŝƪƯŚůƱŵƺŝŵřŻōƭƹżƫçæŢƿŵƹŶŰƯ
ŢǀƘƣƺƯŹŵŹŚĩƪưůƪưƗŻŚƛōŻřƂǀěƾƫřƺţƭři1ŢǀƘƣƺƯ
ƪƤƳƹƪưůƶƬůźƯƭŚưţřƭƹżƫççŢƿŵƹŶŰƯŢſřƾƫřƺţƭři
ŹŵƱōĥŚŤƳƺƯƪưƗŻŚƛōŻřƂǀěƾƫřƺţƭři ŢǀƘƣƺƯŹŵŹŚĩƽřźŝ ŹŵŹŚĩƪǀưĪţƱŚƯŻƶŞſŚŰƯƵƺŰƳçèŢƿŵƹŶŰƯŢſřźųōƶƬůźƯ
ŢƿŵƹŶŰƯŶƷŵƾƯƱŚƄƳřŹĥŚŤƳƺƯƶƬůźƯŹŵƾƫřƺţƭři ŢǀƘƣƺƯ ŻřƂǀěƾƫřƺţƭři1ŢǀƘƣƺƯŹŵĥŚŤƳƺƯŹŚĩƭŚưţřƭƹżƫçé
çæƱŚƿŵƺŞƘƯƲưſŚƿƹƾưţŚůřŹŚſƭŶƤƯƾƬĩƺţŚƋŹŵřĦƳƮǀƷřźŝřƶƫřŶƘſƽŻŚſƵŵŚƯōƱŚƯŻŚŝĥŚŤƳƺƯƾƷŚĭŹŚĩƱŚƿźūƽŶƴŞƳŚƯŻ

ŹŵƾƟŵŚƈºţšŹƺƇƶŝĥŚŤƳƺƯƽŚƷƱŚƯŻƹŢųřƺƴĪƿƖƿŻƺţŚŝ(1,10)
RƹTƽŚºƷźŤƯřŹŚěŶƳƺºƃƾƯŶǀƫƺţŢųřƺƴĪƿƖƿŻƺţŚŝ(1,100)ƵŻŚŝ
ŚºŝƢŝŚƐƯƪƿƺŰţƽŚƷŶƗƺƯƹŶƴƃŚŝƾƯåçƹåêŚŝźŝřźŝŜǀţźţƶŝ
ŶƳƺƃƾƯƲǀǀƘţ[LB(1T



قیمت: تومان


دیدگاهتان را بنویسید