When a company uses a make-to-order or direct-order business model, it needs to keep a low finished goods inventory level to be competitive. However, a low inventory level will cause the company to have little buffer to face the unforeseeable demand surge, which strengthens the close relationship between the stage of production and distribution. This paper probes an integrated production and distribution scheduling problem in which jobs are first produced by a set of unrelated parallel machines and then directly distributed to the corresponding customers by vehicles with limited capacity, with no inventory kept at the production stage. The objective is to find a joint production and distribution schedule such that the total cost, considering both customer service level and total distribution cost, is minimized. This paper integrated the earliest available machine first (EAMF) and variable neighborhood search (VNS) to solve the two-stage scheduling problem and used EAMF, which considers the load of the unrelated parallel machine to generate a set of production schedules to be systematically optimized by VNS, along with optimized routing, and applied a shaking mechanism of VNS to escape from the local optimal solution. The results of the computational experiments showed that the proposed method is better than ant colony optimization (ACO) heuristic methods in the computation time and solution quality.