Поможет очередь задач (task queue).
Надо принимать задание, ставить его в очередь и отдавать ответ типа «принято. номер задания ZZZ» – это выполняется практически мгновенно. Затем нужно узнавать, «готово ли задание ZZZ?» – например, ajax'ом раз в пару секунд опрашивать сервер.
Выполняются задания в один или несколько потоков, на этом или другом сервере, «рабочим» процессом. Запускается рабочий процесс не под веб-сервером, а из командной строки и не имеет ограничений на время выполнения. Процесс либо висит постоянно и ждёт поступления задач, либо запускается по крону раз в N минут (и выполняется в случае если нет другого запущенного процесса с предыдущего раза).
Например, во фреймворке Laravel (и облегченной его версии Lumen) очень хорошая
реализация очереди задач из коробки.
