Aiming　at　the　deadline-constrained　scientific　workflow　scheduling　problem　under　multi-cloud　environment,　the　concept　of　partial　critical　paths　algorithm　is　introduced.　A　cost-driven　scheduling　strategy　for　scientific　workflow　is　proposed　to　reduce　the　execution　cost　of　workflow　as　much　as　possible　and　satisfy　its　deadline　constraint.　The　characteristics　of　multi-cloud　environment　and　scientific　workflows　are　taken　into　account　in　this　strategy.　Firstly,　the　adjacent　two　tasks　with　a　common　directed　cut-edge　are　merged　into　a　single　task　based　on　the　workflow　structure.　Then,　the　partial　critical　paths　with　subdeadline　constraints　are　searched　based　on　the　critical　parent　iterative　mechanism.　Finally,　the　most　suitable　instances　are　allocated　to　the　partial　critical　path　and　all　the　tasks　in　the　path　are　scheduled　to　their　corresponding　instance.　Various　workflows　are　used　for　evaluating　the　proposed　strategy　and　experimental　results　show　that　the　proposed　strategy　has　a　better　execution　efficiency　and　a　lower　workflow　execution　cost.　©　2015,　Journal　of　Pattern　Recognition　and　Artificial　Intelligence.　All　right　reserved.