Scheduling parallel multiple capacitated machines with sequence-dependent constraint

This paper introduces a new kind of parallel machines scheduling problem. Each job has a minimal processing time and all the machines are multiple capacitated machines in this problem. Each machine can process at most β jobs simultaneously according to the First-In-First-Out discipline, and the completion sequence and completion time interval between two jobs are restricted by the plan. A CSP model and a heuristic algorithm are put forward. The algorithm contains two stages, in the first stage, a method of job assignment based on expected starting time is presented; and in the second stage, the timetable is output to minimize the objective function. Computational tests reflect that both the model and the heuristic are feasible and efficient.