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

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.
æèíîçæŶƬūæƵŹŚưƃ ŶǀƫƺţŢƿźƿŶƯƹƖƿŚƴƇƾſŶƴƸƯƾƬƬưƫřƲǀŝƶƿźƄƳ’

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

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

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

ƎſƺŤƯƽŻŚſƶƴǀưĩƝŶƷƹŵŚŝƽřƶƬůźƯƶſĥŚŤƳƺƯƾƷŚĭŹŚĩƱŚƿźūƽŶƴŞƳŚƯŻƶƫŐƀƯƶƫŚƤƯƲƿřŹŵĥŚŤƳƺƯƾƷŚĭŹŚĩƱŚƿźūƶƫŐƀƯ
ƽŚƷƮŤƀǀſŻřƾƫŶƯƶƫŐƀƯƲƿřŵƺƃƾƯƾſŹźŝŚƷŹŚĩŵźĩźƿŵƱŚƯŻƎſƺŤƯƹŚƷŹŚĩƭŚưţřƱŚƯŻŹŚĩƱŚƿźūƱŚƯŻƎſƺŤƯ
žĜſŶƳƺƃƾƯƭŚŬƳřƪƤŤƀƯƹƱŚƯżưƷŹƺƏƶŝƾţƹŚƠŤƯƽŶǀƫƺţšŚǀƬưƗƱōŹŵƶĩŢſřƽŶǀƫƺţ ŵźĩźƿŵƱŚƯŻƎſƺŤƯ ƲƿřŹŵŶƳƺƃƾƯƪƤŤƴƯƾƿŚƸƳšŚǀƬưƗƽřźŝĥŚŤƳƺƯƶƬůźƯƶŝƹƵŶƃƽŹƹōƖưūƽŶǀƫƺţšŚƘƐƣ ƾƫřƺţƶŝƶŤƀŝřƹƽŻŚſƵŵŚƯōƱŚƯŻ
ƢǀƣŵƹƪƯŚĩƁŹŚưƃƪůƽŚƷƁƹŹ ƪƤƳƹƪưůƱŚƯŻƹƾƫřƺţƶŝƶŤƀŝřƹƽŻŚſƵŵŚƯōƱŚƯŻƲŤƟźĭźƔƳŹŵŚŝŢſřƵŶƃƾƘſƩŶƯ ƭŚưţřƱŚƯŻƽřźŝƲǀƿŚěŶůĨƿžĜſŵƺƃĨƿŵżƳƾƘƣřƹƎǀŰƯƶŝƵŶƃƾůřźƏƩŶƯšŚƘƐƣ ŹŵƾƟŵŚƈţšŹƺƇƶŝŚƷŹŚĩƪƿƺŰţŶƗƺƯƶƳƺưƳƽŚƷƶƫŚƀƯƽřźŝƶƯřŵřŹŵŵƺƃƾƯƶŗřŹřŚƷŹŚĩƶǀƬĩ íƺĮƴǀƫƽŻŚſƶƴǀƸŝŹřżƟřƭźƳ ŻřƽŵŚƸƴƄǀěƩŶƯƾŬƴſŹŚŞŤƗřƽřźŝŶƳƺƃƾƯŶǀƫƺţƵŶƃƲǀǀƘţƵŻŚŝ ŵƺƃƾƯƵŵŚƠŤſřŶƿŵźĭƾƀƿƺƳƶƯŚƳźŝ 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
ŚƷŢƿŵƹŶŰƯƹšŚƋƹźƠƯèè
ƾºƯźƿŻŵŹřƺƯƵŶƃƶŤƟźĭźƔƳŹŵƩŶƯƽŚƷŢƿŵƹŶŰƯƹšŚƋƹźƠƯ
ŶƃŚŝ
ŶƴƃŚŝƾƯŽźŤſŵŹŵƽżƿŹƶƯŚƳźŝƢƟřƕƹźƃŹŵŚƷƲǀƃŚƯ 
ŶƴƃŚŝƾƯŽźŤſŵŹŵƽżƿŹƶƯŚƳźŝƢƟřƕƹźƃŹŵŚƷŹŚĩƶưƷ 
ƶºĩƾºƴƘƯƲƿŶŝŶƃŚŝƾưƳŻŚŬƯŚƷšŚǀƬưƗŹŵƾŤƀĪƃĢǀƷ
ŶſźŝƭŚưţřƶŝƶƠƣƹƱƹŶŝŶƿŚŝƵŶƃƕƹźƃšŚǀƬưƗŻřĨƿźƷ 
ŵŹřŶƳŵƺūƹƽŹŚĩƭŚŬƳřƽřźŝƾŤƿƺƫƹřĢǀƷ 
ƲǀƿŚºěŶůƶŞſŚŰƯŮƿźƄţƶŝƭŹŚƸģƂŴŝŹŵŵŻřŵźěƾƯƽŵŚƸƴƄǀě
ƵŵŚƠŤºſřŚŝƮŬƴěƂŴŝŹŵŵƺƃƾƯƶŤųřŵźěƶƫŐƀƯƽřźŝƽŵŚƸƴƄǀě
ƪºůĨºģƺĩƵŻřŶºƳřŹŵƵŶºƃŶºǀƫƺţƪŗŚƀºƯíƺºĮƴǀƫŹřżºƟřƭźƳŻř
ŵƺƃƾƯƱŚǀŝƽźǀĭƶŬǀŤƳżǀƳƮƄƃƂŴŝŹŵŶƳƺƃƾƯ

ƕƺƋƺƯšŚǀŝŵřŹƹźƯç
ƹŵĥŚºŤƳƺƯƾƷŚºĭŹŚĩƱŚºƿźūƶƫŐƀºƯƶºƘƫŚƐƯƶŝ[æ]ƱřŹŚĪưƷƹƾƫ
ŶºƴŤųřŵźěƩƹřƶºƬůźƯŹŵƲǀºƃŚƯçƲŤƟźºĭźºƔƳŹŵŚºŝƽřƶƬůźƯ ƶºſƾƷŚĭŹŚĩƱŚƿźūƽŶƴŞƳŚƯŻƶƫŐƀƯ[ç]žǀƀƿŹŚĜƿŚĩƹŽŚƯ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
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

ƭŚºưţŻřƵŶºƯōŢºſŵƶºŝƽŹŚºĪǀŝƱŚƯŻƲƿźŤƄǀŝéƶƐŝřŹŶƴƳŚưƷ
ƶƐŝřŹƎſƺţĥŚŤƳƺƯƶƬůźƯƽřźŝźƔƳŵŹƺƯŹŚĩŚţƶŤƟźĭŹřźƣƽŚƷŹŚĩ ŶƿōƾƯŢſŵƶŝë
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 ƖºưūŚŝçîƶƐŝřŹƢŝŚƐƯƱřƺţƾƯžĜſ řŹƁŻřŵźºěƱŚºƯŻƽŻŚſƵŵŚƯōƱŚƯŻƲĪưƯŶůƲƿźŤưĩƲǀƃŚƯ ƩƹřƶºƬůźƯŹŵŚºƷƲǀƃŚƯŻřĨƿźƷƽƹŹźŝŚƷŹŚĩŻřƾƫřƺţźƷƽřźŝ
šŚºǀƬưƗŶºƿŚŝƭƹŵƶºƬůźƯŹŵŹŚºĩƕƹźºƃƽřźŝƱƺģŵŹƹōŢſŵƶŝ ŵƺƃƭŚưţƩƹřƶƬůźƯƽŻřƺƯƽŚƷƲǀƃŚƯƭŚưţƽƹŹźŝŚƷŹŚĩŻřĨƿźƷ ƵŶºƯōŢºſŵƶŝŶůƲƿźŤƄǀŝƶŬǀŤƳŹŵŶŝŚƿƵřŹŶƘŝƶƬůźƯƶŝŹŚĩŚţ ƽŚƷƲǀƃŚƯƭŚưţƲǀƿŚěŶůƱřƺƴƗƶŝƩƹřƶƬůźƯƽŚƷƲǀƃŚƯƭŚưţŻř 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

R),LB(1T

R)]źƿŻƶƐŝřŹ
22
åíƹåëåéåçŚºŝźºŝřźŝƝřŶºƷřŜºǀĩźţŢǀưƷřŜƿźƋ ŵŚºƘŝřŚºŝƪŗŚƀºƯƽřźŝřŹƝŶƷźƿŵŚƤƯæƩƹŶūŶƃƶŤƟźĭźƔƳŹŵ íƺºĮƴǀƫƽŻŚºſƶƴǀƸŝŹřżƟřƭźƳƶƬǀſƹƶŝƶĩŶƷŵƾƯƱŚƄƳĨģƺĩ êŻřžºěæƩƹŶūŹŵƵŶƯōŢſŵƶŝźƿŵŚƤƯŶƳřƵŶƃƪůƹŶǀƫƺţ ƵŶºƃƾƟźƘƯśřƺūƱřƺƴƗƶŝíƺĮƴǀƫŹřżƟřƭźƳĨưĩƶŝřźūřŢƗŚſ ƵŶºƃƲǀºǀƘţƽřźºūřƱŚƯŻšŶƯŹŵƶĩƾƬŗŚƀƯŢſřƶūƺţƪŝŚƣŶƳř ƵŵřŵƱŚƄºƳæƩƹŶūŹŵŢƯLjƗŚŝŶƳřƵŶƄƳƲĪưƯƶƤƐƴƯŵŹřƹ íƺĮƴǀƫŹřżƟřƭźƳŻřƵŶƯōŢſŵƶŝƽŚƷśřƺūƶƀƿŚƤƯƽřźŝŶƳřƵŶƃ ŹŵƱōŪƿŚºŤƳƶĩŶºƃƵŵŚƠŤºſřƪƯŚĩƁŹŚưƃƁƹŹŻřæƩƹŶūŹŵ ƱŵřŵƱŚƄºƳƽřźºŝƪƯŚĩƁŹŚưƃƁƹŹŢſřƵŶƃƵŵŹƹōçƩƹŶū ƵŶºƃŶºǀƫƺţƪŗŚƀºƯƽřźŝƵŶƃƭŚŬƳřƽŚƷřźūřƾŤſŹŵƹƩŶƯŹŚŞŤƗř ƽřźºŝƾ޺ſŚƴƯƁƹŹƵŵźºŝƭŚºƳƁƹŹƶºĩƾƫŚůŹŵŶƿŵźĭŵŚƸƴƄǀě ƪºƯŚĩƁŹŚưºƃƁƹŹŹŵŶºƿōƾºưƳŹŚưƃƶŝźţīŹżŝŵŚƘŝřŚŝƪŗŚƀƯ śřƺºūƲƿźŤƸŝƹŶǀƫƺţźƔƳŵŹƺƯƪŗŚƀƯƽřźŝƲĪưƯƽŚƷŢƫŚůƭŚưţ ƹŵƺºūƺƯƽŚºƷƾƫřƺºţƭŚºưţƪºƯŚĩƁŹŚưƃƁƹŹŵƺƃƾƯƾƟźƘƯ
řŹŚºƷƱōĨºţĨºţƝřŶºƷřźƿŵŚºƤƯƹƵŵźưºƃřŹŹŚĩnƽřźŝƲĪưƯ
ƲǀºƃŚƯŵřŶºƘţźºƷŚŝŹŚĩëŢƫŚůŹŵƩŚŨƯƽřźŝŶƿŚưƳƾƯƶŞſŚŰƯ
ƶºĩŵƺºƃƾƯŶǀƫƺţŢƄĮƿŚū6! 720ŵřŶƘţƩƹřƶƬůźƯŹŵƽŻřƺƯ ƹŶºƃŚŝƾºƯŹŚºĩëƽřźºŝƾƫřƺţƲĪưƯƽŚƷŢƫŚůƭŚưţƵŶƳźǀĭźŝŹŵ ŚºƷŢƄĮƿŚūŵřŶƘţŜǀţźţƶŝîƹíìƽŚƷŹŚĩŵřŶƘţƽřźŝƲǀƴĤưƷ
ƹ8! 40320  7! 5040 źºŝřźŝƵŶºƃŶºǀƫƺţƹƲĪưƯƽŚƷƾƫřƺţŚƿ
ƽřźºŝƲĪưƯƽŚƷśřƺūƭŚưţŶǀƫƺţƶƯŚƳźŝŵƺŝŶƷřƺų 9! 362880
ƵŵŚºǀěƹƶŤºƃƺƳMATLAB 7.0.4ŹřżƟřƭźƳŹŵƪƯŚĩƁŹŚưƃŢƫŚů ŢſřƵŶƃƽŻŚſ
ƭźƳĨưĩƶŝƵŶƃŶǀƫƺţƪŗŚƀƯƽŻŚſƵŵŚǀěŪƿŚŤƳæƩƹŶū íƺĮƴǀƫŻŚſƶƴǀƸŝŹřżƟř


n m
ç é ë í
ç æêê æîéçë çìëë èåì
é æêîê çæèæ çéíí
ë

ë í æêíê æëêìè æîéëë æîèéë çèíîë
ççîêè çíæ
çëêë
ç æëéçí çåêéç çéèèì çíéìæ
é æçííí æëëéè çëçç çêèåç
ì

ë í æëîåè
æìëéí æîèëí
çèêéê çëçæì çììçç èåëêé
ç çæéèê çéæçç çêìéì
é æììîë çéæåì çìêîì èéììì
í

ë
í æëæîì

çæíéç
çííéê èèçæç
ç çèåèê èååíë
é çæìçç çìéèê èåéêè
î
ë æîæç
í çîåìè
ŢſŵƶŝƲǀƿŚěŶůƵŶƴƷŵƱŚƄƳèåƶƐŝřŹŵƺƃƾƯśŚŴŤƳřƽŻřƺƯ
ŶƃŚŝƾƯƩƹřƶƬůźƯŹŵƵŶƯō
LBST1  max (SUM MAP (K)) èå
k1,2,..,m
ƶƫŚƀºƯƽřźºŝèæƶºƐŝřŹƢŝŚºƐƯƲǀƿŚºěŶůĨƿƱřƺţƾƯŚƸŤƳřŹŵ ŵřŵŵŚƸƴƄǀě
LB  max{LBST1  min PTj  min PAj
jj
nèæ
,(PTj )  minjPAj} j
j1

ƶºŝŶºůƲƿźŤưĩƵŶƴƷŵƱŚƄƳƩƹřŢưƀƣèæƶƐŝřŹŻřƾƄŴŝŹŵ
ŹŵŹřŶºƤƯƲƿźŤưĩŜǀţźţƶŝƭƹŵŢưƀƣƩƹřƶƬůźƯŹŵƵŶƯōŢſŵ ŻřŶºƘŝƶºĩƾƴƘƯƲƿŶŝŢſřŚƷŹŚĩĥŚŤƳƺƯƹƪƤƳƹƪưůƭŚŬƳřƱŚƯŻ ĥŚŤƳƺƯƹƪƤƳƹƪưůƱŚƯŻƲƿźŤưĩŚŝŹŚĩƶƬƇŚƟLjŝƩƹřƶƬůźƯƭŚŬƳř
n
ƉźºƟƲºƿřźŝƾƴŤŞƯ(PTj )  minjPAj ŢưƀƣŵƺƃƭŚŬƳř
j1
šŚºƘƐƣƭŚºưţŵƺºƃƾºưƳƭŚŬƳřƩƹřƶƬůźƯŹŵƾƬưƗĢǀƷƶĩŢſř ƽŚºƷƱŚºƯŻƕƺºưŬƯƵŶƴƷŵƱŚƄƳƩƹřŢưƀƣŶƳƺƃƾƯƽŹřŶƿźų
źºƔƳŹŵŢºƫŚůƲƿźŤƸŝƵŶƴƷŵƱŚƄƳƭƹŵŢưƀƣƹŚƷŹŚĩƭŚưţƪưů ŢºǀƘƣƺƯƲƿźºųōŹŵƶºĩƽƺŰƳƶŝŢſřƭƺſƶƬůźƯŹŵƵŶƃƶŤƟźĭ
ƱƹŶŝĥŚŤƳƺƯŹŚĩƹŶƃŚŝƶŤƟźĭŹřźƣĥŚŤƳƺƯƱŚƯŻƲƿźŤưĩŚŝŹŚĩƾƫřƺţ
ŵƺƃƕƹźƃƪŞƣƶƬůźƯƹŵŻřžěźǀųŚţ
íƺĮƴǀƫŹřżƟřƭźƳŻřƵŵŚƠŤſřŚŝƩŶƯƪůê
ŻřƂǀºŝƩŶƯŹŵƵŶƃƶŤƟźĭźƔƳŹŵƝřŶƷřŵřŶƘţƶĩƲƿřƶŝƶūƺţŚŝ ŻřƵŶºƃƵŵŚƠŤºſřŹřżºƟřƭźƳŢƿŵƹŶŰƯƶŝƶūƺţŚŝƹŢſřƝŶƷĨƿ ĨƿƶŝƝŶƷƹŵƪƿŶŞţƽřźŝƪůƁƹŹƱřƺƴƗƶŝƝřŶƷřŜǀĩźţƁƹŹ
ƵŶºƃƶºŤƟźĭźºƔƳŹŵƝŶƷƖŝŚţƶŬǀŤƳŹŵŢſřƵŶƃƵŵŚƠŤſřƝŶƷ ŻřŢſřšŹŚŞƗƪůƽřźŝ
F f1  (1) f2 èç
ƝŶºƷƹŚºƷŹŚĩƭŚºưţřƱŚƯŻƎſƺŤƯƽŻŚſƶƴǀưĩ f1 ƩƹřƝŶƷ ŢºſřŚºƷŹŚĩƶºǀƬĩŵźºĩźƿŵƎºſƺŤƯƽŻŚſƶƴǀưĩ f2 ƭƹŵ
ƮǀưƈºţƮǀưƈºţƶºŝƶŤƀºŝƶºĩŶºƃŚŝƾƯĨƿƹźƠƇƲǀŝƽźŤƯřŹŚě
ŵƺƃƾƯƲǀǀƘţƵŶƳźǀĭ ƽŻŚſƶƴǀƸŝŹřżƟřƭźƳƎſƺţƵŶƃƶŗřŹřƾƋŚƿŹƩŶƯƽŻŚſƵŵŚǀěƽřźŝ ŢºſřƵŶºƯōæƩƹŶūŹŵƶĩƾţŚŞǀĩźţŚŝƾĪģƺĩƪŗŚƀƯíƺĮƴǀƫ ƩƹřƶºƬůźƯƲǀƃŚƯmŻřĨƿźƷƽřźŝƁŻřŵźěƽŚƷƱŚƯŻŶƃŶǀƫƺţ ƽŚºƷƱŚºƯŻŢųřƺƴĪƿƖƿŻƺţŚŝ(1,100)ƵŻŚŝŹŵƾƟŵŚƈţšŹƺƇƶŝ ŢºųřƺƴĪƿƖºƿŻƺţŚŝ(1,20) ƵŻŚŝŹŵƾƟŵŚƈţšŹƺƇƶŝƽŻŚſƵŵŚƯō ƵŻŚºŝŹŵƾƟŵŚƈºţšŹƺºƇƶºŝƭƹŵƶºƬůźƯƪºƤƳƹƪưůƽŚƷƱŚƯŻ
ƱŚƿŵƺŞƘƯƲưſŚƿƹƾưţŚůřŹŚſƭŶƤƯƾƬĩƺţŚƋŹŵřĦƳƮǀƷřźŝřƶƫřŶƘſƽŻŚſƵŵŚƯōƱŚƯŻŚŝĥŚŤƳƺƯƾƷŚĭŹŚĩƱŚƿźūƽŶƴŞƳŚƯŻçç

ƽźǀĭƶŬǀŤƳë
ƱŚºƿźūƶƫŐƀºƯƪºůƽřźºŝŶºƿŶūƾºƋŚƿŹƩŶºƯĨƿƶƫŚƤƯƲƿřŹŵ
ƹƪºƤƳƹƪºưůƱŚƯŻƲŤƟźĭźƔƳŹŵŚŝƽřƶƬůźƯƹŵĥŚŤƳƺƯƾƷŚĭŹŚĩ ƹŶºǀƫƺţĨºģƺĩƪŗŚƀƯŶƃƶŗřŹřƾƫřƺţƶŝƶŤƀŝřƹƽŻŚſƵŵŚƯōƱŚƯŻ ŹřżºƟřƭźºƳŻřƵŶºƯōŢºſŵƶŝƽŚƷśřƺūƲǀŝƽřƶƀƿŚƤƯƹŶƃƪů ŻřƾƌºƘŝŹŵŶºƃƭŚŬƳřƪƯŚĩƁŹŚưƃƁƹŹƹíƺĮƴǀƫƽŻŚſƶƴǀƸŝ ƶºƴǀƸŝśřƺºūŚºŝíƺºĮƴǀƫŹřżºƟřƭźƳƾƘƋƺƯƶƴǀƸŝśřƺūŚƷƶƫŐƀƯ ŹŵƾºưĩƝřźºŰƳřŚºƿƵŵƺºŝƱŚƀºĪƿƪƯŚĩƁŹŚưƃƁƹŹŻřƪƇŚů
ŹřżºƟřƭźƳŹŵƕƹźƃƶƐƤƳƶŝƾĮŤƀŝƝLjŤųřƲƿřƶĩŶƳŹřŵêŵƹŶů ƱŚƄºƳƁƹŹƹŵŻřƵŶºƯōŢºſŶŝŪƿŚŤƳƶƀƿŚƤƯƲƿřźŝŚƴŝŵŹřŵíƺĮƴǀƫ
ƁƹŹn>ínŚƷŹŚĩŵřŶºƘţźŤĭŹżŝŵŚƘŝřŚŝƽŚƷƶƫŚƀƯŹŵŶƷŶǀƯ ƶƴǀƸŝźƿŵŚƤƯŻřƝŶƷƖŝŚţźƿŵŚƤƯƝřźŰƳřƹƱŚƯŻźƔƳŻříƺĮƴǀƫƪů īŹżºŝƽŚºƷƶƫŚƀºƯŻřƾƌºƘŝŹŵƶºĪƿŹƺƏƶºŝŢºſřŶƯōŹŚĩŚƳƾƬĩ ƖƟŹƽřźŝƲƿřźŝŚƴŝŶƷŵƾƯƱŚƄƳƝřźŰƳřçåŚţƝŶƷƖŝŚţŹřŶƤƯŹŵ
ƾºƯŵŚƸƴƄºǀěŵŚƿŻƝřźŰƳřŶƇŹŵƹƾƳLJƺƏƽřźūřƱŚƯŻƪĪƄƯƹŵ
Ś ƿƽŹŚ ĪŤŝřƽŚƷƮŤƿŹƺ ĮƫřŻřź ŤĭŹżŝŵŚ ƘŝřŚ ŝƪŗŚƀ ƯŹŵŵƺ ƃ ŵƺƃƵŵŚƠŤſřƽŹŚĪŤŝřřźƟ
ƖūřźƯ
Lee, C.Y., Cheng, T.C.E., Lin, B.M.T., “Minimizing the Makespan in the 3-Machine Assembly-Type Flowshop Scheduling Problem”, Management
Science, Vol. 39, 1993, pp. 616-625.

Koulamas, C., Kyparisis, G., “The Three-Stage Assembly Flowshop Scheduling Problem”, Computers and Operations Research, Vol. 28, 2001, pp. 689-704.

Tozkapan, A., Kirca, O., Chung, C.S., “A Branch and Bound Algorithm to Minimize the Total Weighted
Flowtime for the Two-Stage Assembly Scheduling Problem”, Computers and Operations Research, Vol.
30, 2003, pp. 309-320.

Al-Anzi, F.S., Allahverdi, A., “A Hybrid Tabu Search Heuristic for the Two-Stage Assembly Scheduling Problem”, International Journal of Operations Research, Vol. 3, No. 2, 2006, pp. 109-119.

Allahverdi, A., Al-Anzi, F.S., “A PSO and a Tabu Search Heuristics for the Assembly Scheduling
Problem of the Two-Stage Distributed Database Application”, Computers and Operations Research, Vol. 33, No. 4, 2006, pp. 1056-1080.

Al-Anzi, F.S., Allahverdi, A., “A Self-Adaptive Differential Evolution Heuristic for Two Stage
Assembly Scheduling Problem to Minimize Maximum
Lateness with Setup Times”, European Journal of Operational Research, Vol. 182, 2007, pp.80 94.

Allahverdi, A., Al-Anzi, F.S., “The Two-Stage Assembly Flowshop Scheduling Problem with
Bicriteria of Makespan and Mean Completion Time”, International Journal of Advanced Manufacturing Technology, Vol. 37, No. 1, 2007, pp. 166-177.
ƁƹŹŚŝƵŶƃŶǀƫƺţƪŗŚƀƯƽŻŚſƵŵŚǀěŪƿŚŤƳçƩƹŶū ƪƯŚĩƁŹŚưƃ


n m
ç é ë í
ç æêçæë æîéçë çèéêë çìéíë
é æèììè æìêì çæèæ çéíí
ë

ë í æêæê æêìé æîéëë æîèéë çèìíè
ççîêè çíæ
çëêë
ç æëéçí çåéç çéèèì çíçêé
é æçæìé æëëèé çæåìì çêèåç
ì

ë í æêæçê æêêçå æîèëí æîîíç çèêéê çéèèé çììçç çíêåç
ç æéåèå æìéì çåìí çéåî
é æèîîç æîéíê çéîìì èåéì
í

ë í æéêæç æéæîê æîèèì æîåæê çéæëç çèíèê çííë çíëêê
ç æèêêæ æíéåç çèçêè çíåé
é æêéèæ æîìíé çéæèì çíéìê
î
ë æëêìæ çæëèæ çëëîæ èæìêæ
í æîéåì çéëçé çîíéç èêåçé
ƹæƩƹŶºūŹŵíƺĮƴǀƫŹřżƟřƭźƳŻřƵŶƯōŢſŵƶŝŪƿŚŤƳƶƀƿŚƤƯŚŝ
ƪŗŚƀºƯŹŵƶºĩŢƟŚƿŹŵƱřƺţƾƯçƩƹŶūŹŵƪƯŚĩƁŹŚưƃƁƹŹ źƿŵŚºƤƯŵŹřƺºƯŻřŶƇŹŵêåŹŵíƺĮƴǀƫŹřżƟřƭźƳŚŝƵŶƃƪůƶƳƺưƳ
çèíèê êåæêåæŚººţźŨĩřŶººůƵŶººƯōŢººſŶŝƝŶººƷƖŝŚººţ ƹŶƃŚŝƾƯƪƯŚĩƁŹŚưƃƁƹŹŻřźţŶŝçåŵƹŶůŶůřƹçííéê
ŶºƳřƺţƾºưƳŢƗŚſêřźūřƱŚƯŻŢƃŸĭŻřžěŵŹřƺƯŶƇŹŵçêŹŵ
ŶƿŚưƳŶǀƫƺţƲĪưƯƵŵƹŶŰƯŹŵřŹƾŝřƺū
ƕƺ ººƳŻřƵŶ ººƃƶ ººŤƟźĭźºººƔƳŹŵƩŶ ººƯƶ ººĩƾƿŚºººūƱōŻř
ƶƫŚƀºƯƹŵŻřƾĪƿƾƬĩŢƫŚůƹŶƃŚŝƾƯÎ (AF(m,1,1)//) ƪŗŚƀƯ
ƩŶºƯƱŵƺŝNP_hardƱřƺţƾƯŢſřÐ (AF(m,1)//)ƹ Ï (F3//)
(AF(m,1)//Cmax ) ƶƫŐƀººƯƱŵƺººŝNP_hardźººŝŵŚƴŤººſřŚººŝřŹ
ŶƃŚŝƾƯNP_hardŚƿƺƣƽŵŚƸƴƄǀěƩŶƯƶŬǀŤƳŹŵ[ææƹæ]ŢƟźƿŸě
ŶƃŚŝƾƯƵŶƃšŚŞŧřƶƫŐƀƯŻřƽźţƾƬĩŢƫŚůřźƿŻ
ƲǀºƃŚƯŵřŶºƘţƶĩƾƳŚƯŻƶĩƕƺƋƺƯƲƿřƽƹŹźŝƾſŹźŝŚŝƾƟźƏŻř
źŤƄ ºǀŝèŻř(Fl //) ƾƷŚ ºĭŹŚĩƱŚ ºƿźūƶƫŐƀ ºƯŹŵ(l) Ţ ºŝŚŧ ƾºƯźºĮƿŵŹŚŝ[æç]ŶƃŚŝƾƯNP_hardŚƿƺƣƶƫŐƀƯ(l  3) Ţſř ƵŵŚºƯōƉźºƟśŚƀºŤůřŚºŝźƔƳŵŹƺƯƶƫŐƀƯƱŵƺŝNP_hardƶŝƱřƺţ ƶºǀƫƹřśřƺºūśŚºŴŤƳřƶŝƶūƺţŚŝŵƺưƳƵŹŚƃřƾƫřƺţƶŝƶŤƀŝřƹƽŻŚſ ƺĮƴǀƫŹřżƟřƭźƳŹŵƵŶƃƵŵźŝŹŚĩƶŝƱřźĩƹƶųŚƃŵźĪƿƹŹŹŵƾƟŵŚƈţ
ƱŶºƃřŶºǀ쏌ºƔŤƳřƱřƺºţƾƯźƔƳŵŹƺƯƶƫŐƀƯƱŵƺŝNP_hardƹí
ŢƃřŵřŹƾƬŰƯƶƴǀƸŝƾŤůƱŶƄƳŢƟŚƿŚƿƹƾƬŰƯƶƴǀƸŝ
ƹƭƹŵƶƬůźƯŹŵƲǀƃŚƯĨƿƩƹřƶƬůźƯŹŵƲǀƃŚƯmŚŝƽřƶƬůźƯƶſƾƷŚĭŹŚĩƱŚƿźū1 ƭƺſ
ƽźſƶƴǀƃŚƯƶſƾƷŚĭŹŚĩƱŚƿźū2
ƭƹŵƶƬůźƯŹŵƲǀƃŚƯĨƿƩƹřƶƬůźƯŹŵƲǀƃŚƯmŚŝƽřƶƬůźƯƹŵƾƷŚĭŹŚĩƱŚƿźū3
çèƱŚƿŵƺŞƘƯƲưſŚƿƹƾưţŚůřŹŚſƭŶƤƯƾƬĩƺţŚƋŹŵřĦƳƮǀƷřźŝřƶƫřŶƘſƽŻŚſƵŵŚƯōƱŚƯŻŚŝĥŚŤƳƺƯƾƷŚĭŹŚĩƱŚƿźūƽŶƴŞƳŚƯŻ

Shim, S.O., Kim, Y.D., “Minimizing Total Tardiness in an Unrelated Parallel- Machine Scheduling Problem”, Journal of the Operational Research Society, Vol. 58, 2007, pp. 346-354.

Rabadi, G., Mollaghasemi, M., Anagnostopoulos, G.C., “A Branch-and-Bound Algorithm for the
Early/tardy Machine Scheduling Problem with a
Common Due-Date and Sequence-Dependent Setup Time”, Computers and Operations Research, Vol. 31, 2004, pp. 1727-1751.

Gendreau, M., Laporte, L., Guimaraes, E.M., “A
DivideandMergeHeuristic for the Multiprocessor
SchedulingProblemwithSequenceDependentSetup Times”, European Journal of Operational Research, Vol. 133, 2001, pp. 183-189.

Potts, C.N., Sevast’janov, S.V., Strusevich, V.A., Van Wassenhove, L.N., Zwaneveld, C.M., “The Two-Stage
Assembly Scheduling Problem: Complexity and Approximation”, Operations Research, Vol. 43, 1995, pp. 346-355.

Garey, M.R., Johnson, D.S., Sethi, R., “The Complexity of Flowshop and Jobshop Scheduling”, Mathematics of Operations Research, Vol. 1, 1976, pp. 117-129.



قیمت: تومان


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