# Blocking Cyclic Job-Shop Scheduling Problems
## 1 Introduction  
This study is concerned with a manufacturing system, namely cyclic job shop with blocking conditions. The cyclic job-shop scheduling problem is an extension of the well-known job-shop scheduling problem (JSSP) [1, 2]. The original JSSP involves scheduling jobs, each of which consist of a number of operations, and the objective is to minimise the length of the schedule, or the _makespan_. Moreover, manufacturing systems often require schedules that are cyclic in nature and leading to additional complexities [3, 4]. Cyclic or periodic scheduling produce schedules that are executed repeatedly in exactly the same manner on one or more machines [5]. The objective functions mainly used in cyclic scheduling are minimising _cycle time_, _work-in-process_, and mixes of them. The cycle time is the time period between two successive occurrences of the same operations, and the work-in-process is the number of jobs processed at the same time. The aim of cyclic scheduling in this research is to find a schedule with the minimum cycle time (common in manufacturing systems) [6]. Within the system, a set of jobs, known as the minimal part set (MPS) (For example, if the requirements are 1000 parts of type A, 3000 parts of type B and 2000 parts of type C, the MPS can be chosen as (A, B, B, B, C, C) and we repeat the production of the same MPS 1000 times.) is executed cyclically, in order to meet production requirements [7, 8]. Referring to parts as jobs, for each MPS, the jobs go through the machines in exactly the same pattern, and each machine thereby processes the operations in an identical way in each cycle. An alternative view is that a single MPS is sent into a production line where exactly one MPS is completed and unloaded from it. The primary performance measure is the cycle time, or equivalently its reciprocal, the throughput rate, which measures how often the MPSs areproduced in a fixed time interval. The JSSP itself is known to be among the most complex combinatorial optimisation problems [9], and the cyclic variant considered in this study incorporates further complexity. Moreover, in several manufacturing systems, there exist production processes where no intermediate buffers exist between machines due to technical requirements or process characteristics. In the context of the JSSP, this implies that a job that completes processing on a machine has to remain on the same machine until the next machine in sequence is available for processing. Since the job cannot leave the machine that it is executing on, it effectively blocks the machine by not allowing other parts to enter it. In the literature, this is referred to as a _blocking condition_, which this study is also concerned with. Figure 1 presents an example of a blocking condition where job 1 (processing time of 30 units) needs to be processed on machine 1 followed by machine 2. We see in Figure 1, if machine 2 is available to load and start executing job 1 when job 1 completes, then job 1 immediately moves to machine 2. Machine 1 is now available for other incoming jobs. However, if machine 2 is busy when job 1 is ready to move (Figure 1), then job 1 stays on machine 1 thereby blocking it until machine 2 becomes free. Hence, machine 1 is also blocked for the time period that job 1 stays on it. There are several well-studied scheduling problems with blocking conditions, including the manufacturing of concrete blocks [10], scheduling in the chemical industry [11], scheduling in the iron and steel industry [12], industrial waste and the manufacturing of metallic parts [13], and train scheduling [14]. A production line, structured as a job shop requires that: \((i)\) the operations of each job of the MPS are assigned to the machines in advance and \((ii)\) the routing (order of processing) of each job passing through the machines, not necessarily the same for each job, is known and fixed. The aim of the cyclic JSSP is to find the processing order in which the operations are repetitively processed on each machine a very large number of times.