They knew that they would miss the prayer on the plane so they prayed a few minutes before the time for it began
Question

I was on a long journey and we were in a European airport. The time for the plane to take off was also the time for Zuhr prayer to begin, according to the prayer timetable for that city. Before we got on board the plane, ten minutes before takeoff, we prayed Zuhr and ‘Asr with some other brothers. One of the brothers criticized us and told us that we should have prayed on board the plane after making sure that the time for prayer had begun. Is our prayer valid, knowing that there was no suitable place for praying on the plane and we were going to arrive in our country at night?.
Praise be to Allah.Firstly: 
It is permissible for a traveller to join Zuhr and ‘Asr, and Maghrib and ‘Isha’, at the time of the earlier or later prayer, according to whatever is easier for him.  
Secondly: 
There are set times for the five daily prayers, the beginning and end of which are clearly defined, as Allah says (interpretation of the meaning): 
“Verily, As‑Salaah (the prayer) is enjoined on the believers at fixed hours”
[al-Nisa’ 4:103]
i.e., there are set times for it, and it is not permissible for the Muslim to offer any prayer before the time for it has begun. If he does that, it is not valid, according to scholarly consensus. 
Based on this, you have to repeat Zuhr and ‘Asr, because you offered them before the time for them began. 
Shaykh Ibn ‘Uthaymeen (may Allah have mercy on him) was asked about the ruling on offering a prayer before the time for it has begun. 
He replied: 
Offering a prayer before the time for it has begun is not valid, even if it was only one minute before the time for it. If a person says the opening takbeer before the time, then his prayer is not valid, because Allah says (interpretation of the meaning):
“Verily, As‑Salaah (the prayer) is enjoined on the believers at fixed hours”
[al-Nisa’ 4:103]
i.e., strictly-defined times. So the prayer is not valid if it is offered before its time, and the prayer that you offered before its time must be repeated. And Allah is the source of strength. End quote from Majmoo’ Fataawa al-Shaykh Ibn ‘Uthaymeen (12/216). 
He also said: Prayer is not valid if done before its time, according to the consensus of the Muslims. If a person offers a prayer ahead of time, if he did that deliberately then his prayer is invalid, and he is not free of sin. If he did not do it deliberately, because he thought that the time for it had begun, then he is not a sinner, and his prayer is regarded as naafil (supererogatory), but he has to repeat it, because one of the conditions of prayer is that the time for it should have begun. End quote from al-Sharh al-Mumti’. 
Thirdly: 
If the time for prayer has begun and the traveller knows that the plane will not land until after the time for prayer has ended – as in your case – then he should pray on board the plane because of necessity, and it is not permissible for him to delay the prayer until the time for it is over.  
He should offer the prayer on board the plane according to what he is able to do of standing, bowing, prostrating and facing the qiblah. It is better for someone in your position to offer the prayer on board the plane as soon as the time for prayer begins, before the plane moves, because that will let him focus more fully on the prayer. In that case it may be possible to stand, bow, prostrate and face the qiblah.  
It says in Fataawa al-Lajnah al-Daa’imah (8/102): Question: If I am travelling in a plane and the time for prayer comes, is it permissible for me to pray in the plane or not? 
Answer: If the time for prayer comes when the plane is still flying, and you fear that the time for prayer may end before it lands in the airport, then the scholars are unanimously agreed that it is obligatory to offer the prayer according to what you are able to do of standing, bowing, prostrating and facing the qiblah, because Allah says (interpretation of the meaning): 
“So keep your duty to Allah and fear Him as much as you can”
[al-Taghaabun 64:16]
And the Prophet (peace and blessings of Allah be upon him) said: “If I command you to do a thing, do as much of it as you can.” Narrated by Muslim (1337). 
But if it is known that the plane will land before the time for prayer ends, and there will be enough time to offer the prayer, or if the prayer is one of those that may be joined with another, such as Zuhr with ‘Asr or Maghrib with ‘Isha’, or it is known that the plane will land before the end of the time for the second prayer and there will be enough time to offer the prayer, then the majority of scholars are of the view that it is permissible to offer the prayer on board the plane, because of the command to offer the prayer when the time for it begins according to what one is able to do, as stated above. This is the correct view. End quote. 
It also says (8/126): Question: Is it permissible to pray sitting on board a plane, although one is able to stand, out of shyness? 
Answer: It is not permissible to pray sitting on board a plane or elsewhere when one is able to stand, because of the general meaning of the words of Allah (interpretation of the meaning): “And stand before Allah with obedience” {al-Baqarah 2:238], and because of the hadeeth of ‘Imraan ibn Husayn which is narrated in Saheeh al-Bukhaari, according to which the Prophet (peace and blessings of Allah be upon him) said to him: “pray standing, and if you cannot, then sitting, and if you cannot, then on your side.” Al-Nasaa’i added with a saheeh isnaad: “And if you cannot then lying on your back.”  End quote.  
And Allah knows best.