This study optimizes truck scheduling for transporting perishable products considering demand uncertainty. The supply chain of perishable goods is complex due to the critical importance of quality to consumers and presents significant logistical distribution challenges that must be managed effectively. The approach proposed here uses cross-docking, a popular strategy that reduces inventory levels and shortens delivery times. We develop a non-deterministic bi-objective mathematical programming model to minimize cost and time objectives. Minimizing product quality degradation is implicitly included in the cost-related objective function. The model also considers the uncertainty. Also, in the proposed model, which is defined in a multi-period environment, the types of trucks and the loading and unloading times required for each type of product are specified. Considering these parameters together distinguishes this model from existing cross-docking models. For small-sized problems, CPLEX Optimizer provides accurate solutions. For large problems, NSGA-II is used. Comparing CPLEX and NSGA-II on small problems shows no significant performance difference. CPLEX is superior in exact solutions, while NSGA-II is better at considering different alternatives in multi-objective scenarios, showing how they complement each other in optimization. Input parameters are optimized using the Taguchi method to evaluate their impact on NSGA-II. Sensitivity analysis showed that key parameters significantly affect delay and cost, contributing to 22-25% and 12-15% variations, respectively. It is worth noting that increasing product variety has the most significant impact on the total delay weight. Overall, this model increases service flexibility, reduces wasted time, improves customer satisfaction and service level, and ultimately increases profitability.