Inventory Order Scheduling Optimization: Capacity-Constrained Fulfillment Window Allocation in Perishable Subscription E-Commerce

We introduce the Capacity-Aware Perishable Fulfillment Scheduling (CAPFS) problem, a new class of combinatorial scheduling problem arising when subscription e-commerce orders must be assigned to weekday shipping slots under three simultaneous constraints: hard daily capacity limits at parallel fulfillment centers, customer-specific food-continuity deadlines derived from perishable on-hand inventory buffers, and order-type heterogeneity (trial versus regular) imposing asymmetric feasibility structures. We prove CAPFS is NP-hard by polynomial-time reduction from parallel machine scheduling with deadlines and weighted tardiness (Pm|r_j,d_j|ΣwjTj). We develop a MILP formulation with a multi-objective function covering capacity overload, aggregate stockout risk, and schedule lateness, alongside a polynomial O(n log n) Least-Slack Priority (LSP) heuristic with a provable structural safety property: early-order moves reduce both objectives simultaneously. Applied to 3,851 real meal-kit orders across two fulfillment centers in August 2020, the incumbent transit-time heuristic generates Tuesday overloads of 192–233% of capacity while Monday operates at 9–53% utilization — Jain Fairness Index 0.30–0.51 against a target of ≥0.90. The LSP heuristic achieves a 48.4% reduction in total capacity overload and 29.0%