It helps if you have the crystarium grid maxed out or close to being maxed out for this fight. I think I used buffs for this fight, I'm unsure about it.

This is how I beat Barthandelus the first time; my strategy may be able to help you.

I had Snow, Lightning, and Hope for this fight.

Once the battle began I had Hope buffing the party, Lightning as a Medic, and Snow as a Commando. Once the buffs (Protect and Shell mainly) are applied switch to the Diversity Paradigm: Snow as Com, Lightning as Rav, and Hope as Med. I worked my way left to right taking down the different parts. Diversity should be work throughout taking down Barthandelus' parts.

Once you can attack Barthandelus' head, rotate between Relentless Assault, Diversity (to heal), and Hero's Charge (to re-apply the buffs). Once Barthandelus begins to charge up for "Destrudo" there are two ways to go about:

1) Keep wailing on Barthandelus with Relentless Assault till Barthandelus flinches; this will look as if he being knocked back. Destrudo is an attack that needs to be charged up. If the party keeps attacking while Barthandelus is charging up and is able to "knock back" Barthandelus the power to Destrudo will greatly be reduced. Once Barthandelus has been "knocked back" switch to the Combat Clinic Paradigm to heal up and to wait for Destrudo.

2) Once Destrudo comes up on screen switch to Combat Clinic, heal up quickly (one or two rounds of healing should be good), then switch to Relentless Assault. Wail on Barthandelus and "knock" him back. Switch to Combat Clinic to prepare for Destrudo.

Now, you can get a few more licks after you have knocked Barthandelus back before Destrudo goes off just don't over-extend your attack. Perhaps trying to count how long it takes for Destrudo to go off after his has been "knocked back" could help you know when to switch to Combat Clinic if you decide to get a few more licks.

After Destrudo goes off, heal up, then attack him and heal when needed.

You don't need to Summon in this battle - I didn't - and I did make it a little bit under the target time. If you want to attempt to getter a better "star-rating" then go ahead and summon, but they are not vital to succes. With my strategy Barthandelus never casted Doom on me.

Good Luck.