Unfortunately, with your lack of details, it will take a much stronger mind-reader hat than mine is to give you a reasonable guess -- but there might be a monk with better ESP skills than I have.

• I am assuming by "executes lines", you mean executing lines of source code, not parsing lines of a data file. But that is just an assumption
• Perl executes code in the order defined by the logic of the code; unless there is a difference in the logic (or the inputs that control the logic), it should execute in proper order
• Are there a lot of random variables (either created by rand, or because of not-determined-by-the-program inputs? That could explain change in order
• Is the code iterating through a %hash or $hashref? The order of keys and each are not guaranteed to be the same from run-to-run or from machine-to-machine. This is my best guess.
• Is it possible to provide clues in the form of a SSCCE? It doesn't have to be the same data or the same code, as long as it shows the same issue -- replace real data with facts about disney characters or automobiles or fruit or something; strip out all the irrelevant code until you have the shortest possible example which still shows things being executed "out of order". Include copious print statements, to show the state of input or state-control variables. If possible, grab output from your SSCCE run on different machines (or different runs) that show this change in the execution order.
• pre-create update: I just saw the Anonymous Monk post, and STDOUT vs STDERR is another excellent idea to check.