The European shoe industry has experienced significant challenges in the last 20 years, mainly due to the pressures of modern global markets in which the industry has to compete with competitors from low labour cost countries in Asia and the Far East. A new trend is now forecast concerning the mass customisation of shoes, where customers choose and order customised shoes from a range of predefined materials and designs. This is to be achieved through the ‘shoe shop of the future’ with combined capabilities of obtaining 3D models of customer’s feet together with the exciting developments offered through the latest advancement in e-commerce. However, such a novel approach for the customisation of shoe design and production will have a significant influence on the batch sizes and expected lead times, and will reduce the average batch size of shoe production from 500–1000 pairs to about 10–20 pairs per batch. Consequently, customised shoes will result in an enormous increase in the number of batches, leading to an increase in the complexity of planning, scheduling and tracking of orders both across the supply chain and internally within various production departments of a shoe factory. This research proposes a distributed scheduling approach to provide the required autonomy in decision making and flexibility in job sequencing at departmental level to deal with the complexity of planning a large number of small batch production orders.