To begin with, it is a major sin because "killing an innocent is the same as killing every human beings". This is the philosophy of 'murdering' in Islam. This is entirely relative to fate - I will come back to this later on.
Fate is not a movie scenario.
Think of fate as a network or a web. There are tens, hundreds, thousands and millions of different posibilities available.
The only known fact of fate is that we will all return to him / we will die. But, which road we take to the end of the line is entirely up to us. But of course Allah knows which path we will take. - that is a different matter.
Scenario: I can choose to jump out my window right now and die. Now Allah knows what I will do but it is not forced upon us. Does that make sense? If it was forced - if everything was written and we had no freedom of choice - there would be no judgement; as a result no purpose for humans.
Even simpler: I'm currently thirsty, Allah knows when I will drink water but I still yet to decide.
Now back to your question.
If that is so, that means the murder of the person was already written by Allah in his fate and had Allah's acceptance. Then why it is considered major sin?
When you kill someone, you actually interfere with their fate. Not only their fate but the entire fate running of from that person - Example: the persons kids, grandkids, and the line goes on until the end of time.
Back to what I wrote at the top - "killing an innocent is the same as killing every human beings"
If we were to travel back in time and killed the first born human - Adam, there would be no humans.
[Allah knows best]