Abstract: Parked vehicle assisted edge computing (PVEC) is effective to alleviate the imbalance between supply and demand of resources in vehicular edge computing, by utilizing the idle resources in parked vehicles (PVs). However, the computing services provided by the PVs can be abruptly aborted due to uncertain parking behaviours. This makes it hard to meet the requirements of users on service reliability. To address this issue, this paper formulates an optimization problem for service reliability guarantee. Then, a task replication technique is introduced to transform the formulated problem into a replication offloading problem, with the goal of minimizing the average completion time of task replications. The NP-hardness of the formulated problem is proved. A greedy algorithm (GA) is proposed to solve the formulated problem, by carefully offloading the replicas of the tasks with large data sizes to the PVs, which can provide the computing services with service guarantee and short completion time. Meanwhile, an enhanced genetic algorithm (EGA) is proposed to refine the solution generated by the proposed algorithm GA. Experimental results show that the proposed GA and EGA algorithms outperform the baseline algorithms in terms of the average completion time of task replications for different requirements of users on service reliability.