We consider a picking and packing process, which is organized on several production lines, each devoted to its types of products. All lines are equipped with identical parallel machines and an intermediate buffer between picking and packing zones. We know the set of orders which have to be processed through the warehouse. Each order consists of several boxes. For each box, we know the list of types of items and their amounts. For each box, we also know the production line where it has to be processed. All boxes have to go through the picking stage, followed by the packing stage (hybrid flow-shop model). The time interval between the start of the first box from the order at the picking stage and the end of packing of the last box from the same order cannot exceed the given threshold. We need to find a scheduling with minimal makespan.

Picking stage of each production line is organized as follows. We have several parking slots, where the pallets with raw material can be located. Each pallet can occupy one slot. The picking from the pallet is possible if and only if it is parked in a slot. There is also a fixed number of slots for universal carriage (UC). These UC serve as temporary storage of already picked boxes. Each UC corresponds to exactly one box. As soon as all the contents of the box are picked into the UC, it should be moved to the packing stage or an intermediate buffer and replaced by a new empty UC. The picking machines work in parallel. They have parallel access to all pallets in the parking slots, but each machine can process only one pallet and one box at a time. Each box can be processed by one machine at a time. But one pallet can be used by several machines at the same time. If one or more pallets needed for the current box are not located on the parking slots, the picking process is produced for other pallets and paused. This picking machine is blocked until the required pallets will come to the packing slots. The picking process is serviced by a limited fleet of transportation robots. They deliver raw materials from the storage to picking zone and back.

Problem Formulation