Optimised scheduling in human–robot collaboration – a use case in the assembly of printed circuit boards

Abstract

Advances in the technologies of sensors and lightweight robots increasingly enable direct physical interaction between humans and robots. This so-called human–robot collaboration is supposed to offer more flexibility in production processes, as opposed to fully automated processes. The aim of this contribution is to describe an integer linear programming model which optimally coordinates the distribution of tasks between humans and robots in a realistic production process of printed circuit boards (PCBs), where the objective is to minimise the completion time of a board. In addition, we discuss an extended case wherein a whole set of different boards is to be assembled, which is highly relevant for low volume production with a high degree of customisation. After stating an extended integer linear programming (ILP) formulation, we propose two practical approaches for solving the computationally more complex second scenario: an order-based heuristic approach and a matheuristic applying a truncated variant of the ILP model with different sequencing strategies. The computational evaluation based on a real-world use case from the PCB industry underlines the efficacy of the matheuristic approach for obtaining a good overall makespan.

Keywords:

• human–robot collaboration
• multi-mode resource constrained project scheduling problem
• ILP
• matheuristic
• PCB assembly

1. Introduction

Advances in the technologies of sensors and lightweight robots have led to the belief that robots can work alongside humans within close proximity, without causing any danger to the human worker. This is often referred to as direct human–robot interaction (HRI) or human–robot collaboration (HRC) if human and robot directly work together towards a common goal (see Wang, Törngren, and Onori (2015) for a wider perspective). Today, due to strict safety regulations, HRI and HRC are often limited to theoretical or laboratory applications. Nonetheless, the possible advantages of HRI and HRC have been discussed for a wide range of areas such as military and rescue missions (Kim, Chacha, and Shah 2015), space missions (Singer and Akin 2010), domestic and health care, as well as manufacturing of aircrafts (Levine and Williams 2014), electronic parts and automobiles (Unhelkar, Siu, and Shah 2014). Additional work was done by Taylor (2016) who describes the role of collaborative robotics and group effort. On the one hand, HR collaboration promises to offer more flexibility in production processes, compared to fully automated processes. On the other hand, robotic precision and mechanical strength may reduce costly errors in production and relieve humans of strenuous physical work (Tsarouchi, Makris, and Chryssolouris 2016).

From a production planning perspective, the optimal utilisation of the robots’ capabilities in their collaboration with human workers poses an interesting challenge. It brings new elements into the established field of scheduling problems since human workers are considered to be more flexible and thus perform some tasks faster than robots, while for other more standardised tasks humans may perform slower than robots. The high cost of investment for installing robotic systems favors production systems where one, or a small number of robots are shared between several work stations manned with human operators. Thus, decisions have to be made regarding which tasks should be performed by a robot and which tasks should be left to the human workers respecting change-over times, temporal and spatial safety distances, and of course the precedence relations implied by the technical production specifications.

This paper deals with the optimal assignment of tasks to a collaborative human–robot team in a production process of assembling printed circuit boards (PCB). It successfully handles a use case originating from a real-world problem in the assembly of PCBs at Zollner Elektronik¹ in Vác, Hungary. Within the PCB production process, the insertion of different components into the PCB and soldering thereof were especially considered. However, the underlying optimisation challenges are fairly general scheduling problems and our solution approaches can serve as starting points for handling also more general production situations.

Two different scenarios are considered. In scenario (1), the objective is to minimise the makespan of assembling one PCB. In scenario (2), an entire sequence of possibly different PCBs is to be assembled, where several PCBs may be processed in parallel, and the makespan is defined by whichever PCB is finished last. The first scenario aims at a low to medium-sized batch production, rather than high volume productions, most of which are fully automated already. The second scenario is highly relevant for even smaller batch sizes down to a lot size of 1, which is receiving more and more interest due to a general increase in demand of customised products, as argued by e.g. Brunetti et al. (2014), Feitzinger and Lee (1997). It also applies to the production of new prototypes, which naturally come in very small numbers. While the saving obtained from the optimisation of a small batch of PCBs may not be worth the effort, the reduced makespan for each PCB in a longer sequence of different boards clearly improves the overall utilisation of a production facility.

Large-scale PCB assembly processes have been extensively investigated from an optimisation perspective. A survey with a hierarchical structure of the main planning tasks in a PCB production system was given by Crama, van de Klundert, and Spieksma (2002). The improvement of single-type PCB production by optimising the automated assembly machinery is described in Grunow et al. (2004). The optimisation issues arising in the automated placement of electronic components on a PCB was considered in two surveys, Ayob and Kendall (2008, 2009). Ayob and Kendall (2008) also point out that the complexity of these problems has led to a somewhat popular strategy of dividing the problem into subproblems of manageable sizes, as we will do by introducing our matheuristic approach. Some technical issues of robots in PCB assembly, in particular for human–robot collaboration, were pointed out in Ruggeri et al. (2017), which also proposes new robot technologies for these tasks.

Optimising the PCB assembly in our use case poses an interesting problem due to its already mentioned complexity. It involves processing multiple parts, each consisting of a series of tasks, and precedence relations between them. Considering human workers and robots as the sole resources required for processing tasks, the problem can be identified as a simplification of the multi mode resource constrained project scheduling problem (MRCPSP). Additional constraints, such as minimum distance requirements and waiting times for agents, are added in order to enhance the fluency of the mixed HR team.

The contribution of the paper is threefold: First of all, we present integer linear programming (ILP) models for both scenarios taking into account the specific constraints imposed by the collaborative setting. Secondly, because of the computational difficulty of solving these models, we also present constructive heuristics for finding effective production sequences taking into account the different capabilities of robots and humans. Finally, we take a truncated version of the ILP model to design a matheuristic for scenario (2). The latter turns out to be a very reasonable compromise between quality of solutions and computational running time. For the real-world-based use cases of our experiments, the matheuristic provides satisfying solutions within an acceptable running time and can be recommended as the method of choice.

The paper is structured as follows. Section 2 will give a compact overview of related literature regarding the topics MRCPSP and human–robot collaboration. Section 3 will describe the ILP model for solving the problem of producing a single PCB. This will be followed by an extension of the ILP model in Section 4, which will optimise the production of an entire sequence of different PCBs. Section 5 will cover different heuristic and matheuristic approaches for both problems discussed. Note that the models and algorithms developed in Sections 3–5 are fairly general and will apply to many collaborative human–robot planning problems. A detailed description of the use case considered with the technical details of the PCB assembly process will be given in Section 6, together with the presentation of the computational test results which are summarised and discussed in Section 6.4. The paper ends with conclusions and pointers to future research in Section 7.

2. Related literature

Many production scheduling problems can be classified as a typical machine scheduling problem, where n jobs have to be scheduled on a given number of m machines. However, in the case considered in this paper, the machine, which in our case is either a robot or a human worker, a job needs to be processed by, might be fixed or may be chosen freely, depending on the job. If the machine is not fixed, the processing times may vary across the different machines. Thus, a trade-off arises between the machine chosen and the time needed to process the job. This problem is tackled by the multi mode resource constrained project scheduling problem. Since the first proposal of an exact solution approach made by Talbot (1982), many different exact and metaheuristic approaches have been analysed, see e.g. Hartmann and Drexl (1998) and Kolisch and Hartmann (2006). Another extensive literature review of metaheuristic methods to solve the MRCPSP is provided by Van Peteghem and Vanhoucke (2014). We assume, like many others, that all tasks are non-preemptive with deterministic processing times. A survey on project scheduling problems that include uncertainty can be found in Herroelen and Leus (2005). Regarding the resource constraint only, our problem is equivalent to the flexible job shop scheduling problem. Surveys on this topic can be found in Wang (2005) and Chaudhry and Khan (2016). However, the flexible job shop problem does not consider precedence relations between different jobs. Due to this fact and the additional constraints needed for the human–robot collaboration, the MRCPSP representation was chosen to formulate the given problem. It should be noted that our problem is also closely related to the multi mode multiprocessor scheduling problem as considered by Bianco et al. (1999). However, in their setting the notion of multi mode is more general since a mode allows the successive usage of several agents (=machines) for processing a task, while in our setting only one of the agents has to be selected.

Although our problem is rooted in scheduling, it also contains aspects of task allocation in multi-robot systems. This area has been treated extensively in the last decade as illustrated by several taxonomies (see below) which try to bring an overall view into the vast body of literature. In our setting, human workers and robots are both seen as available agents, and these could be considered as entities in a multi-robot system. According to the widely used taxonomy for multi-robot task allocation (MRTA) proposed by Gerkey and Mataric (2004), we are faced with single-task robots (ST), and our focus is on single-robot tasks (SR), although we also mention the extension to multi-robots tasks (MR) requiring more than one agent (in our case, a human and a robot). The planning perspective is off-line with all information available from the beginning, i.e. a time-extended assignment of tasks (TA). Concerning the objective function, it turns out that our minimisation of the makespan, i.e. the maximum completion time, is not adequately represented by the utility models which sum up utilities accrued by each task-robot allocation. Note that (Gerkey and Mataric 2004, Section 5.2.1) points to an Alliance Efficiency Problem, where the maximum completion time over several robots is considered. Looking at the extended taxonomy by Korsah, Stentz, and Dias (2013), our setting corresponds more closely to the case of cross-schedule dependencies (XD), since the makespan is affected by the schedule of all tasks. As we do above, also (Korsah, Stentz, and Dias 2013, Section 5.3.2) points to the multi mode scheduling problem as a related problem. Summarising, we might classify our problem as a distant relative of the MRTA class XD [ST-SR-TA] (and also XD [ST-MR-TA]), but with additional constraints such as precedence relations, waiting times and dependencies between tasks.

A recent overview by Nunes et al. (2017) (see also Gini (2017)), containing a wealth of references, extends the MRTA taxonomy (Gerkey and Mataric 2004) to include temporal and ordering constraints (TOC). Temporal constraints permit time windows for tasks, which are not an issue in our setting. Ordering constraints include precedence constraints (as they occur in our problem) but also synchronisation constraints where specific points in time are involved. Thus, our problem could be classified as a relative of [ST-SR-TA:SP]. The authors also distinguish between hard constraints and soft constraints whose violation is feasible, but incurs a penalty. A number of objective functions is listed, including the makespan minimisation. Interruptions and other unforeseen events are considered as dynamics of the planning task. A survey of solution methods also points to the necessity of heuristic approaches since MILP models are mostly intractable for larger problem sizes (Nunes et al. 2017). Note that the definition of OR-predecessor groups considered in our problem (see Section 3) is not included in this recent and wide-ranging survey, but constitutes a new aspect in multi-robot task allocation. A very special situation of task groups is considered by Luo, Chakraborty, and Sycara (2011). Tasks are partitioned into groups with precedence relations between groups, and robots can perform only one task from each group. The special feature of intermediate storage of parts (see (14(14) )) is also a new aspect not considered in the literature before.

A larger scale perspective is pursued by Zhang and Shah (2016), where on an upper level agents are assigned to different workplaces, i.e. separate locations corresponding to a flow-shop type production scenario. This strategic planning issue of assigning (a large number of) agents to different phases of the production is not relevant for the setting we are dealing with. But similar to our problem, there arises for each workplace the subproblem of assigning tasks to agents and finally, the resulting task scheduling problem. This multi-level optimisation problem can be described by a single MILP-model, but it is dealt with by a so-called multi-abstraction search approach. The Tercio Algorithm from Gombolay, Wilcox, and Shah (2013) is used as a subroutine to solve the task assignment and scheduling problem.

A further taxonomy of multi-robot systems is due to Dudek, Jenkin, and Milios (2002). However, their approach focuses on the architecture of robotic systems emphasising communication and topology, which do not play a role in our problem.

The temporal planning of human and robot activities lies at the core of our production scheduling problem. Recently, there has been increasing interest in how to deal with temporal aspects in collaborative settings involving multiple agents in general and human–robot interaction in particular (Yan, Jouandeau, and Cherif 2013). Representing activities over time is often done by a Temporal Network (TN) (Holme and Saramäki 2012), where each activity (or task) is associated with two node-time points (e.g. start and end time) and additional constraints are given on the arcs connecting two nodes of the network. A Simple Temporal Network (STN) allows for no more than one interval restriction on the time period between any two time points in the network. STNs provide the starting point to deal with temporal constraints in planning and scheduling problems. Checking for loops or negative cycles in STN is important for proving the feasibility of a certain scheduling task and for ruling out inconsistencies (Dechter, Meiri, and Pearl 1991). However, in our production setting feasibility is guaranteed from the underlying industrial process. Disjunctive Temporal Constraint Networks (DTCNs) have been used as a basis for tackling more complex task assignment problems by considering the temporal properties of all possible assignments of tasks to agents, in order to select the best overall plan (Shah and Williams 2008). A scheduling problem for robotic assistance systems in manual manufacturing processes was treated by Wilcox, Nikolaidis, and Julie (2012). The different tasks performed by humans entail frequent changes of preferences and require a dynamic and adaptive robotic scheduling strategy. For this setting a so-called Adaptive Preferences Algorithm is introduced based on a Simple Temporal Problem with Preferences (Wilcox, Nikolaidis, and Julie 2012).

Beside temporal aspects of collaboration, the presence of moving robots in a shared physical space also requires spatial constraints to be considered. Recently, Gombolay et al. studied collaborative teams with multiple robots moving and working in the same physical space (Gombolay, Wilcox, and Shah 2013). They formulated the task assignment and scheduling problem as a mixed-integer linear program (MILP), an example of a centralised method which can achieve optimal results. However, centralised strategies are not suitable for field operations where communication can be unreliable. Therefore, a decentralised approach based on auctions is chosen in Nunes and Gini (2015).

Studies have also been done by Elprama et al. (2017) to investigate how workers are reacting when robots are to be installed in their factory. An important aspect for human robot collaboration concerns the level of control assumed over the human workers. In our setting, it will be assumed that all human decisions are controllable and fully deterministic as workers follow a strict protocol. However, in many applications, human decisions are independent and uncontrollable. For such cases Levine and Williams (2014) developed a control methodology called Pike, which allows a robot to simultaneously recognise the plan of a human being and, derived from it, perform a desired or subsequently required activity to achieve the overall production goal. Alami et al. (2006) encoded task specific constraints that enable a prediction of human actions.

A recent experimental study on human–robot collaboration was done by Gombolay et al. (2017). Their paper considers the human situational awareness, workload allocation and human workflow preferences. The underlying formal scheduling problem of their study is formulated as an involved, time-indexed ILP model not unlike our approach in Section 3 and solved by the Tercio Algorithm as in Gombolay, Wilcox, and Shah (2013).

Collaborative robotics can also be seen as a special case of multi-agent planning. In this field heuristics are the most commonly applied methods (Ephrati and Rosenschein 1997). A widely adopted approach is the application of local search heuristics in each agent, but recently also global heuristics (Torreno, Sapena, and Onaindia 2015) were applied to tackle the problem. As a real-world example of a multi-agent system, Rosenfeld et al. describe the successful deployment of a multi-robot system in a warehouse (Rosenfeld et al. 2016). There, the requirement is to move merchandise and equipment from one place to another in collaboration with human workers. In their work, they provide a new approach of utilising automated advising agents for assisting a human worker to better manage time and workload.

A different area of research in robotics deals with path planning and movement optimisation. Note that this may also include the optimal scheduling of tasks for finding an effective sequence of movements. Alatartsev et al. give an extensive literature review regarding different path planning approaches (Alatartsev, Stellmacher, and Ortmeier 2015). They also describe several levels of related planning problems in robotics, such as the determination of the most efficient number of robots employed for a certain production line and their collision free and obstacle avoiding path planning. They also emphasise the importance of combining the task planning, which concerns the optimal handling of objects, with the path planning between those tasks or objects, in order to achieve a coherent plan.

3. Single board problem

In the following we will introduce the notation for the single board problem and introduce an ILP formulation. Some additional conditions will be discussed at the end of the section.

An instance of the single board problem comprises the following main input parameters. Additional input data will be introduced together with the respective constraints in the ILP model.

• V Set of all tasks j that need to be processed

• T Set of all time points t within the considered time frame

• A Set of all available agents m

• Set of all human workers

• Set of all robots

• Set of all AND-predecessor tasks i of task j

• Set of all OR-predecessor groups c of task j

• Set of all OR-predecessor tasks i in group c of task j

• Number of tasks in set , which have to be processed before starting task j

• D Set of all task pairs (i, j), that do not meet the minimum safety distance requirement

• processing time of agent m for task j (will be set to M, if m cannot perform task j)

In order to determine a schedule with minimal makespan for the given problem, the following decision variables are introduced:

With this setting a solution, or schedule, is completely represented by the values of its variables , whereas the variables and are used to establish the order of executing two tasks i and j. In particular, variables and will be used to exclude the parallel execution of two tasks i and j if this is ruled out by certain temporal or spatial safety constraints. These appear in the PCB production problem, but may easily be encountered also in other application scenarios.

The mathematical formulation of an ILP model for the single board problem is presented below. Notation not yet introduced will be described later in the text.(1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11) (12)

First of all, the objective function (1(1) ) minimises the makespan , which is defined by the latest completion time of all tasks j in (2(2) ). Constraints (3(3) ) ensure that all tasks j are started at exactly one time point t within the planning horizon by one of the agents m. By constraints (4(4) ) it is ensured that every agent processes only one task at a time. Through an additional waiting time may be specified for agent m after having processed task j. Since every agent is equivalent to exactly one processing mode, this is a simplification of the resource constraints usually found in resource constrained project scheduling problems.

In order to enforce the AND-precedence relations, constraints (5(5) ) guarantee that any successor task j is not started until its predecessor task i has been finished and the minimum waiting time between both tasks – in order to e.g. allow soldering points to cool down, as is occurs in the PCB assembly process – has passed. Constraints (6(6) ) and (7(7) ) enforce the OR-precedence relations for every OR-predecessor group c of a task j. This means that every task may have more than one OR-predecessor group. For every group c the set of possible OR-predecessors is defined, out of which only tasks actually need to precede task j. Constraints (7(7) ) ensure that at least as many variables take value 1 as the number of tasks which have to be finished before task j may start. If so, constraint (6(6) ) gets enforced for the corresponding OR-predecessor i, where M is defined as a sufficiently large number (i.e. larger than the latest time point considered). Thus, the constraint is also satisfied for all possible starting times for any task i, if i is not chosen as an actual predecessor. Similarly, constraints (9(9) ) ensure that either or take value 1, such that the corresponding constraint of type (8(8) ) gets enforced. This guarantees that any two tasks i and j, that do not meet the minimum distance requirement, are processed successively rather than simultaneously. Finally, the binary decision variables are defined by (10(10) )–(12(12) ).

Two additional constraints from practice in the PCB production can be incorporated into the model as follows. First, if the case occurs that a human worker and a robot have to simultaneously work on one task, then this task is virtually split into two separate tasks i and j, where i can only be processed by humans and j can only be processed by robots. The set of constraints (13(13) ) then ensures for any such pair that both tasks start at the same time, so that they are processed simultaneously. This allows the human and the robot to directly collaborate with each other on the given task. Note that this direct collaboration is frequently considered also in the general multi-robot literature (see e.g. Gerkey and Mataric (2004)).(13)

A second condition found in PCB production but also occurring in other production scheduling problems (cf. Chrobak et al. (2001)) concerns the intermediate storage of parts in a buffer on the workspace. In certain production settings parts have to be picked and prepared before they are actually built into the product. In the meantime, they are stored in a buffer storage of limited capacity Z. In this case, we have to balance the tasks , which add one part into the buffer, and the number of tasks , which remove one part from the buffer. This can be formulated by the following constraints:(14)

In our computational experiments and in the heuristic approaches this condition was not included as our industrial partner found ways to set Z large enough.

4. Sequence of boards problem

This section will cover an extension of the case where, instead of just one board, an entire sequence of different boards, each of them with individual specifications, is to be produced. This setting is highly relevant for low volume production where single boards are considered in the planning process and the contribution of human workers is still significant. Clearly, for high volume production orders, classical batch processing strategies and a higher level of automation are implemented. We will first explain the set-up of the production process before discussing the necessary adaptations of the ILP model.

4.1. Problem description

The objective of this problem is the minimisation of the makespan of an entire sequence of PCBs, where each PCB possibly needs a different set of tasks to be fulfilled. The set of agents is assumed to consist of a set of humans working in parallel and a set of collaborative robots. Each human can only process one board at a time until all tasks of that board are finished. The robots may interchangeably process tasks on different boards, but require some time to switch from one board to another, since the boards are located at different workstations. Each workstation can be associated with exactly one human worker, who is responsible for setting up the blank board at their workstation and for setting it aside to a designated area for finished boards after its assembly. The human worker stays at the same workstation during the entire production process and does not switch between tasks on different boards unless a board is finished. A possible set-up of workstations is sketched in Figure 1. This is only a schematic picture visualising a setting where three human workers, each of them with a dedicated workspace, collaborate with one robot. Clearly, many other, more complicated configurations can be considered as well.

Figure 1. Set-up of working environment with three human workers and one robot.

4.2. ILP extension

In order to formulate the extended problem, some additional decision variables are introduced. First, binary variables take value 1 if and only if board k is assigned to human worker m (17(17) ). Then every board k out of the set of all boards U must be assigned to exactly one of the human workers (15(15) ). A human worker m may only process tasks j of a board k, as defined by the set , that is actually assigned to m (16(16) ). Note that robots may process all tasks, regardless of which human agent the corresponding board is assigned to (given that the robot exhibits the necessary capabilities).(15) (16) (17)

Secondly, since human workers may not interchangeably process tasks on different boards, another ordering variable is introduced. If two boards k and l are both assigned to the same human worker, either or takes value 1 (18(18) ). And thirdly, an earliest start time (19(19) ) and latest end time (20(20) ) must be determined for every board. Then, depending on whether board k shall precede board l or the other way around, takes value 1 and it must hold that or vice versa, with taking value 1 (21(21) 22(22) ).(18) (19) (20) (21) (22)

Robots, however, are allowed to switch between multiple boards that are simultaneously processed by different human workers. But whenever a robot does so, this requires some switching time W and the robot may not process any operations during the W time periods, that it takes to switch from one board to another. So, if a robot starts an operation on board l at time point t, then any operation on another board k, that was processed before by this robot, must have started at the latest at time (23(23) ).(23)

In addition to this model, which represents the situation given in our use case, we will now discuss generalisations and extensions of our objective function. These shall illustrate the possibility of extending the model to other practical problems within a human–robot collaboration environment and may be used as inspiration for further research on the matter.

A relevant addition to the objective is the reduction of the number of tasks performed by robots, as stated by the objective function (24(24) ). Assuming that a high level of sensory precision is needed for the robot to setup on a new task, damages are more likely to occur the more different tasks the robots need to process.(24)

Here, is a factor on the importance of limiting the number of robotic tasks. Equivalently, one can minimise the number of physically strenuous tasks performed by humans by simply replacing the summation over by , with being the set of strenuous tasks, and by .

For similar reasons, another objective asks for the minimisation of the number of switches of robots between boards. The binary variable takes value 1 if and only if some robot must move from a board with task i to another board with task j, which shall be avoided. Constraint (25(25) ) forces to take value 1 if no other task g is processed by robot m in between the two tasks i and j, which are situated on two different boards k and l. However, the makespan shall also be kept in check, which can be controlled by varying the factor in objective function (26(26) ).(25) (26)

In constraint (23(23) ), we assumed the switching time W of robots between boards to be constant. However, it is also of practical relevance to consider variable switching times depending on the distance between boards k and l. These also represent board-dependent setup times or time required for changing the equipment of a robot. They can be modelled by simply replacing W in (23(23) ) by .

Moving one step further, even a task-dependent switching effort can be taken into account. We will consider the case where an agent has to perform certain cleaning, retooling or preparatory operations when the agent processes task j after task i, and no other task in between. These switching operations cause an effort (or cost) and require a certain setup time in which the agent is busy, but other tasks could be performed by other agents during that time. These setup times could also include the switching times for robots between boards, if tasks i and j are on different boards. Recall that human workers remain assigned to one board.

For this scenario, a binary variable takes value 1 if and only if some agent m performs task j immediately after task i, and no other task g is started in between by that agent, as enforced by constraints (27(27) ). The feasible starting time of a task j after task i including the setup time , if both tasks are performed by the same agent, is bounded by (28(28) ).(27) (28) (29)

The objective function (29(29) ) then combines the total setup effort, weighted by factor , with the makespan.

5. Heuristic approaches

Alternatively to the optimisation models, simple heuristics are proposed to obtain reasonably good solutions for the considered problems within a short running time. Since the ILP model is unable to find any feasible solution for the sequence of boards problem within a time limit of four hours, we also propose a matheuristic approach as an addition to the purely heuristic approach for the sequence of boards problem.

We will state the heuristic approaches for arbitrary sets of human workers H and robots R. However, for our computational experiments in Section 6 we follow the PCB assembly use case and restrict ourselves to the real-world scenario of one human worker and one robot in the single board problem and two human workers and one collaborative robot in the sequence of boards problem.

5.1. Single board heuristic

The single board heuristic combines both a priority rule for the order in which the tasks shall be assigned and a rule for prioritising the mode/agent a task shall be assigned to. This section will describe this approach in further detail. It also builds the basis for the sequence of boards heuristic, to be discussed in the next section.

First, all available tasks (i.e. all of its predecessors have been finished) are sorted in decreasing order of the sum of minimal (among all agents that might perform the task) processing times of itself and all its (AND-)successors. This priority rule amounts to computing the longest path from each vertex to the sink in an acyclic graph. This priority rule was already proposed as the ‘Maximum Remaining Work’ rule, by Boctor (1993), where it achieved the best performance out of the seven different priority rules tested on MRCPSP instances. For the set of OR-predecessors of a task j it is still undecided at this point which of them will be designated predecessors of j. To include these OR-predecessors in the decision, we simply take the first tasks² of each set and use them as tentative predecessors of j. Based on the ‘Shortest Feasible Mode with Conditional Wait for the Fastest Mode’ priority rule introduced by Colak, Agarwal, and Erenguc (2013), each task is then assigned to the best agent out of all currently available agents, unless an earlier completion time can be achieved for that task by assigning it to the agent with the shortest processing time as soon as that agent becomes available again. Whenever a task is assigned, the processing agent is marked as unavailable for the required time periods after the task is started and the next task is chosen according to the updated priorities of all remaining tasks. The next point in time considered as a possible starting time for the next task is then equal to the earliest time point that any one of the agents is available. If at that time none of the tasks are available, the time point considered is increased to the point that at least one task becomes available. In case a task is to be processed simultaneously by a human worker and a robot, the task is assigned at the earliest possible time, when both a human and a robot are available.

5.2. Sequence of boards heuristic

The heuristic approach for the sequence of boards problem first determines the order in which the boards are to be scheduled before the individual tasks are assigned. The scheduling of the individual tasks then follows the procedure of the single board heuristic. The tasks are considered in decreasing order of their priority and assigned to either the fastest agent or the earliest available agent. However, some additional modifications are needed to correctly represent the changed scenario as defined in Section 4.1. Once the first task of a board is assigned, all tasks belonging to that board are assigned. Only after all tasks of that board are assigned, the tasks of the next board, as defined by the sequence, are considered. Again, this is done in decreasing order of the tasks’ priorities. Also, when a task of a board is the first one to be assigned to a human worker, the processing times of all other humans for tasks of that board are set to M. In this way it is ensured that no human worker interchangeably processes tasks belonging to different boards and each board is only processed by one human worker.

The following strategies for determining the sequence of the boards are evaluated regarding their ability to produce a good overall makespan:

(1)	(a) Longest Processing Time (LPT): The boards are sorted in decreasing order of the sum of the minimal processing times, over all agents, of all tasks belonging to that board. (b) Shortest Processing Time (SPT): The boards are sorted in increasing order of the sum of the minimal processing times, over all agents, of all tasks belonging to that board. (c) Alternating (ALT): The boards are sorted alternating the longest and the shortest processing time of a board, as defined by (5.2) and (5.2). I.e. the board with the longest processing time is scheduled first, followed by the board with the shortest processing time, followed by the board with the second longest processing time and so forth. This strategy is meant for the case of only two human workers, where it might be able to distribute the boards more evenly by consecutively scheduling short and long boards, so that the overall makespan of both human workers is comparable.
(2)	The boards are sorted dynamically depending on the relative time saving of a robot compared to a human worker (assuming robots are more valuable/scarce than the available human workers). This means that we try to estimate the gain in time obtained from using a robot for a certain board instead of delegating all tasks to a human. Therefore, we define the following subsets of the set for every board k: with , and assuming that the processing times of a task are the same for all humans/all robots (but not necessarily the same for humans and robots). Then the time saving () of a robot on board k may be calculated in the following ways: (a) (b) (c) , where are relative weights for the likelihood and the amount of time saved when a robot is chosen for that task as opposed to the time needed when the task is assigned to a human worker instead. Strategies (2a) and (2b) focus on the actual time saved, whereas strategy (2c) focuses rather on the absolute duration a robot could possibly spend on all tasks. The boards are then sorted in such a way that the overall time gain of all boards that are simultaneously processed is balanced throughout the process.
(3)	(a) The boards are sorted randomly (RND1). (b) The boards are sorted according to 10 different randomly generated permutations (RND10). For each ordering the production schedule is computed and finally the solution with the smallest makespan over all 10 options is chosen.

The idea behind strategy (LPT) is to avoid having long boards at the end of the production process, so that neither robots nor all other human workers are idle at the end. In contrast to that, strategy (SPT) is expected to perform rather weakly.

Whereas strategies (1) and (3) are static, so that the sequence of boards is fixed upfront, strategies (2) are dynamic. This shall be explained further for the example of the use case, where two boards may be processed simultaneously. In the beginning, only the first board with a high time gain by the robot is chosen. Only after all tasks of a board have been scheduled, the next board (in this case with a low time gain by the robot) is chosen, one by one. This allows the simultaneous scheduling of two complementing boards, that is a combination of one board highly depending on the robot (i.e. with a high time gain of the robot) and a second board mainly requiring the skills of a human worker (i.e. with a low time gain of the robot). Depending on whether the currently (i.e. at the time that the other board is finished) processed board has a high (low) robot utilisation, the next board chosen shall have a low (high) robot utilisation. In this context, ‘high’ is defined as above the mean over all boards. Therefore, strategies (2) should result in a balanced distribution of robot workload throughout the entire process and also imply an efficient distribution of the robotic resource. For the more general setting of more humans or robots, one would have to evenly balance the workload of the more critical resource type, depending on their number and skills. The random sorting of boards as suggested by strategies (3) is used as a comparison in order to benchmark the quality of the other strategies.

5.3. Matheuristic approach for a sequence of boards

Instead of optimising the whole sequence of PCBs as in the ILP model, only |H| boards, which can be simultaneously processed, are considered at every iteration of the matheuristic. By only optimising |H| boards at a time, the time horizon considered can be shortened. Together with a reduction in the amount of tasks considered, this leads to a considerable reduction in the amount of decision variables and therefore run time needed to solve the problem. The objective in every iteration is the minimisation of the sum of completion times of the |H| boards, so that the robot’s capabilities are hopefully split in a fair and therefore efficient way between them. For simplicity, we restrict our description to the case of three human workers, but it can be equivalently applied to any number of workers.

Figure 2 outlines the first two iterations of the matheuristic. After every iteration, the schedule gets cut off at the minimal completion time of all boards, with all assignments already started before this point in time being fixed. In the next iteration the remaining tasks of the unfinished boards get re-optimised, together with the tasks of the newly added board. In case that any task of an unfinished board is currently being processed when the schedule is cut off (as illustrated by the grey shaded areas of jobs i and j of Boards 1 and 3 in Figure 2(b)), the assigned agent receives a delayed release date for the next iteration. In our example of Figure 2, this means that for the first time units of the next iteration, the agent, who processed task j, may not process any tasks as to insure that no agent processes two tasks at the same time. The same restriction is enforced on the agent who processes board 1 for the remaining processing time of task i.

In the same way, it is ensured that the robot’s switching time from one board to another is accounted for. Hence, if the first task in an iteration does not belong to the same board as the task the robot processed last (in the preceding iteration), the robot again receives a delayed release date for the remaining switching time after the schedule was cut off. The starting times obtained within every iteration are then increased by the sum of the minimal completion times from all prior iterations. The larger the number of employed human workers, the smaller the time interval of cutting off the schedule becomes. Therefore, this approach is well suited for problems with a small number of humans (as considered in the computational experiments of Section 6, where ) but will become less efficient with an increased number of human workers and also tasks.

Figure 2. Matheuristic approach.

A critical issue is the definition of the sequence, in which the boards are considered. Although the sequence has a substantial impact on the makespan, no particular strategy for sequencing the boards seems to guarantee a good overall makespan. The following strategies were considered: LPT, SPT, ALT and RND1 as introduced in Section 5.2. In order to evenly distribute the robot’s workload, a strategy , focused on the robot’s gain in time relative to the human, was also considered. Due to the fact that in the matheuristic the sequence of boards needed to be generated in advance of scheduling any board, the sequence generated by strategy (2c) was considered, since it performed slightly better than the other time gain measures (2a) and (2b).

However, due to the complex structure of the problem, the results vary considerably for the different strategies when tested on different instances, as will be discussed further in Section 6.3.

6. Computational tests

Before the results of the computational tests will be presented for the different models, the technical specifications of the PCB production process are explained together with a description of the test instance generation. The heuristic approach was implemented in Matlab R2016b and run on a standard PC (Windows 10-64 Bit Intel Core i5-6500, 3.2 GHz CPU, 8 GB RAM). Both ILP models as well as the matheuristic approach were implemented in FICO’s Xpress³ Optimization Suite IVE 8.0 and run on a standard PC (Windows 7-64 Bit Intel Core i5-4590, 3.3 GHz CPU, 8 GB RAM).

6.1. PCB assembly and generation of test instances

Within the PCB production process we focus on the insertion and soldering of different components into the PCB. In the initial scenario, a set of roughly 30 components, including resistors, coils, diodes, USB ports, bridges, skirting boards, optocouplers and microprocessors, were to be inserted. The different components were divided into three groups, depending on their number of electrical pins, which can be assumed to be the main influence on the processing time. The first group consists of all small parts with two pins, such as bridges, resistors and coils. The second and third group is made up of medium resp. large parts, which feature more than two and up to 24 pins each, e.g. optocouplers and microprocessors.

For each component to be inserted onto the blank board, four tasks have to be fulfilled. First, the adjacent wire of each component is bent into the right position. Then, the component is placed onto the PCB (i.e. the actual insertion step). The third step is to solder the pins and in a last step any excess wire is cut off. The order in which these steps are fulfilled must always be followed. Additionally, before any medium or large component can be inserted, all tasks for the corresponding skirting board must have been finished. In our initial scenario, developed jointly with the partner company, we specified that one 20kOhm resistor, one coil and two 20MOhm resistors need to be installed before a bridge can be inserted. Since there were 15 identical 20kOhm resistors, one could choose which one of these was to be installed before a bridge. Similarly, one could choose the particular coil and 20MOhm resistor out of a set of 2 resp. 10 identical components. But eventually all components have to be inserted.

In the single board case, the number of parts within the three groups was randomly and independently chosen from the uniform distribution in the ranges [10, 15], [5, 10] and [2, 5], respectively. In the multiple boards case the number of parts for the three groups were drawn from the uniform distribution with ranges [4, 8], [2, 4] and [1, 2]. Furthermore, any part in groups 1 or 2 may be a predecessor of another part in a subsequent group, with the number of predecessors and the concerned parts being randomly chosen as well. With a 30 probability, the last regular task of a board is a collaborative task which must be simultaneously processed by a human and a robot and is therefore split into two subtasks. By s up the blank board and setting aside the finished board, this results in up to 123 tasks in the single board case. To slightly reduce the complexity in the multiple boards case, tasks 1 and 2 of each part were combined into one task. This leads to up to 45 tasks for each board in the multiple boards case, where 10 boards shall be assembled in one instance. The generated test instances and the full details of the generation process are available on request from the authors.

In order to analyse the effect of changing the robot’s capabilities in comparison to the human skills, three categories of instances were constructed. Category 1 represents the scenario where the robot’s abilities are quite limited. Thus, the robot can only process a small subset of tasks, which, however, may not be processed by a human worker. In category 2 the robot and the human worker(s) are able to perform almost all tasks. However, the time needed to process them varies greatly for the different types of agents depending on each task. In the third category the robotic and the human skill sets are greatly enhanced, such that the robot’s skills are quite comparable to the ones of the human(s) and vice versa. In all categories there are always some tasks, which are processed faster by the humans, and others, which are processed faster by the robot, as there would be little need for cooperation otherwise. The processing time for each task is then the product of a constant value between 1 and 6 (depending on the agent and task of the particular part) and the number of pin pairs. This results in integer processing times between 1 and 40 time units, where one time unit represents about 20 seconds of real processing time. However, large parts with processing times of up to 40 time units are very rare, so that the mean processing time is close to 4 time units. In the single board case, the end of the time frame T considered was set to the sum of the minimal (over all agents) processing times of all tasks plus a buffer of 50 time units (resulting in ). The set of agents in the single board case consisted of one human worker and one robot. For the matheuristic the planning horizon considered in every iteration was set to 250 time units and the set of agents consisted of two human workers and one collaborative robot.

6.2. Results for the single board problem

The computation results for the single board problem are shown in Table 1. Out of the 30 instances one instance in both category 2 and category 3 could not be solved to optimality by the ILP within a time limit of 4 hours. For these two instances, the best found solution was accepted instead. The values shown in the table represent the average obtained over all 10 instances within each category. Whereas the heuristic works reasonably well in category 1, in category 3 and especially 2, the results obtained by the ILP are much better. Due to the strategy of the heuristic, a task with a higher priority may be assigned to a slow agent if no faster agent is available for some time. However, it might be preferable with respect to the makespan to process other tasks with a lower priority first in order to obtain a better agent-task assignment. When the agent-task assignment is quite clear, as in category 1, the ILP model finds an optimal solution within 8 minutes on average. However, the ILP run time increases drastically when the human and robot skill sets converge, whereas the run time of the heuristic remains unchanged.

Table 1. Comparison between the heuristic (H) and the ILP model for the single board problem. Averages are taken over 10 instances.

	av.		Deviation from H to ILP in			av. run time in sec.
Category	ILP	H	av.	max	min	ILP	H
1	159.6	188.3	18.46	24.26	16.43	462	0.008
2	128.7	174.9	36.82	46.08	26.32	3181	0.008
3	128.9	162.1	26.42	33.04	20.00	3575	0.010

6.3. Results for the sequence of boards problem

The computational results for the different sorting strategies in the multiple boards heuristic are given in Table 2(a). The values represent the average deviation in of every strategy’s solution value from the best heuristic solution value found in each instance. The average is taken over all 10 instances within each category. The number of instances in which each strategy’s solution is equal to the best strategy’s solution is also given (see column ). Generating 10 random sequences and accepting the best thereof achieves a better solution than all the other sorting strategies in most instances. Out of the more systematic approaches the LPT and ALT rules perform the best. With regard to the different time gain strategies, strategy (2c) obtains slightly better results than the other two, considering all categories.

Table 2(b) shows the average deviation for every heuristic strategy to the best matheuristic strategy’s solution. As for the single board problem, it can be seen that the heuristic approach works better for categories 1 and 3 than for category 2. It is clearly confirmed that the matheuristic offers a tremendous improvement over all heuristic approaches and can be recommended as the method of choice. Comparing the gaps between heuristic and proven optimal solutions for the single board case (Table 1) with the gaps to the matheuristics in the multiple board case (Table 2(b)), one could infer that the optimality gap of the matheuristic is quite small, say less than 5% on average, but of course this is not a statistically correct conclusion.

Table 2(c) shows the average deviation for every heuristic strategy to the average solution generated by all matheuristic strategies. As can be seen in Figure 3(a), the matheuristic solutions in category 1 vary quite insignificantly over the different sorting strategies. Therefore, the improvement in the performance, when comparing the heuristic solution to the average instead of the best matheuristic solution, is larger in categories 2 and 3 than for category 1. Looking at the results of all categories, as displayed in Figure 3, it becomes evident, that no sorting strategy dominates the others on all instances. But the comparison of the relative deviation from each strategy to the best strategy in each instance, as shown in Table 4, reveals that on average the rules ALT and LPT outperform the other strategies.

Setting the running time in every iteration of the matheuristic to a maximum of 15 minutes before accepting the best found solution, on average 2.14 (resp. 2.05 and 1.85) hours are needed to solve an entire instance of category 1 (resp. 2 and 3). The heuristic, on the other hand, generates solutions in less than six seconds for strategy RND10 and in less than a second for all other strategies.

Table 2. Comparison of the different sorting strategies in the heuristic approach for the multiple boards problem (deviation in ).

(a) Average deviation of each strategy
from the best heuristic strategy and the number () of times it was the best out of all strategies in that instance
	Category 1		Category 2		Category 3
Strategy	Av. Dev.		Av. Dev.		Av. Dev.
LPT	1.08	1	3.09	1	2.78	3
SPT	1.34	2	6.83	1	7.42	0
(a)	2.56	0	5.15	0	3.73	2
(b)	2.56	0	5.15	0	3.38	1
(c)	2.01	0	3.95	1	4.21	0
RND1	1.18	1	6.05	0	5.11	0
RND10	0.04	8	0.59	5	1.12	5
(b) Average deviation of each strategy from the best matheuristic solution
	Category
Strategy	1	2	3
LPT	19.13	27.21	22.18
SPT	19.63	31.05	27.39
(a)	20.79	29.41	23.40
(b)	20.74	29.68	23.13
(b)	19.98	26.77	22.79
RND1	21.33	28.27	24.95
RND10	17.89	24.49	20.57
(c) Average deviation of each strategy from the average matheuristic solution
	Category
Strategy	1	2	3
LPT	16.68	18.80	18.69
SPT	17.00	23.19	24.04
(a)	18.40	21.28	19.88
(b)	18.40	21.28	19.44
(c)	17.76	19.84	20.41
RND1	16.81	22.33	21.44
RND10	15.49	15.99	16.83

Table 3. Average idle times for the heuristic and matheuristic approach (in time units). Averages are taken over all instances and over all heuristic approaches.

	Category	Human 1	Human 2	Robot
Matheuristic	1	275	279	50
	2	58	57	65
	3	35	27	34
Heuristic	1	441	467	61
	2	182	150	58
	3	162	139	49

Figure 3 displays the different makespan results when presorting the boards with the respective strategies for all instances in each category. Given the amelioration in the agents’ capabilities the makespan can be improved around resp. across categories. Beside the far better makespan results, another advantage of the matheuristic approach over the heuristic lies in the even distribution of workload between the different agents. As can be seen in Table 3, the idle times of both human workers and the robot are well-balanced in the matheuristic, whereas the human workers remain under-utilised in the heuristic approach. Note, that the under-utilisation of the human workers in category 1 is not a result of poor scheduling, but stems, to a large extent, from the limited capabilities of the agents. So in this particular case, given the amount of tasks and the distribution of the respective processing times between agents, the general setup of the production process (with two human workers and one robot) might not be optimal.

Figure 3. Comparison of the different presorting strategies over all 10 instances.

Table 4. Average deviation of each matheuristic strategy to the best matheuristic strategy in and the number of instances () in which each strategy found the best solution out of all strategies.

	Category 1		Category 2		Category 3		Total
Strategy	Av. Dev.		Av. Dev.		Av. Dev.		Av. Dev.
LPT	1.89	2	3.44	2	3.03	1	2.79	5
SPT	3.33	3	10.64	0	2.90	3	5.62	6
	2.08	1	8.85	2	3.06	2	4.66	5
RND1	1.76	1	10.21	3	1.99	2	4.65	6

The matheuristic can also be used to optimise larger scale production problems. Extending the sequence of boards to be scheduled from a number of 10 to 20 boards and solving it with one of the strategies, it can be shown that the matheuristic scales up very well since the running time does not increase by much more than a factor of two. It must be noted, however, that due to the time-indexed formulation, the amount of variables and therefore run time needed to solve the problem, heavily depends on the number and processing times of the tasks. Furthermore, setting an appropriate time limit for each iteration poses a challenge.

6.4. Summary and discussion of results

We performed computational experiments on test instances modeled according to the real-world situation of a PCB production process.

Considering the single board situation, where 123 tasks have to be scheduled for one board, 28 out of 30 instances could be solved to optimality by our ILP model within the running time bound of 4 hours, taking less than one hour on average. The more different the abilities of human worker and robot, the smaller the solution times of the ILP. Our priority rule-based heuristic is very fast, but misses the optimal solution by a considerable margin of roughly 20% to 30%. This allows two implications:

(1)	Applying an ILP model is a reasonable option if running time is not too tight, since the optimal solutions delivered by the ILP can be expected to be considerably better than a heuristic.
(2)	If running time is a crucial issue, one should devote more effort into a sophisticated, bespoke heuristic in order to narrow the gap to the optimal solution.

For the multi board situation, each of our 30 instances consists of a sequence of 10 boards, each of them comprising up to 45 tasks. Our experiments compare different sequencing heuristics and the matheuristic which iteratively solves subproblems to optimality by an ILP model. Concerning the sequencing heuristic, it turns out that none of the different sorting strategies gives a significant advantage. Instead, simply taking the best of 10 random sequences in most cases gives the best solution among the sequencing heuristics. The running time of these algorithms is negligible.

However, these heuristic solutions are consistently worse than the matheuristic solutions by a margin of 20% to 30%. Clearly, this advantage of the matheuristic comes at the expense of much higher running times. These depend on the time limit set for the solution of each subproblem. In our setting, a total running time of roughly 2 hours can be expected for the solution of one instance.

Although none of the tested sorting strategies clearly outperformed the others, one could state that the LPT strategy led to the most stable results, when comparing the average deviation from the best solution.

An ‘educated guess’ seems to indicate that the (unknown) gap between the optimal solutions and the matheuristics solutions determined with our time bounds is below 5%. Setting tighter time limits would lead to a loss of solution quality. The matheuristic scales up very well since by construction its running time increases only linearly with the number of boards per instance.

Summarising, we can formulate the following implications for the multi board scenario:

(1)	When applying a heuristic for each single board, the rule for sequencing boards has only minor impact on the final makespan. Thus, taking the best of several different sequences is a fast and simple, yet promising recipe.
(2)	Applying an ILP model for the tasks of each board as a matheuristic gives much better results than the heuristics, but consumes considerable running time.
(3)	In practice, the usage of this matheuristic requires sufficient experiments on relevant test instances to figure out the acceptable trade-off between computation time and solution quality.

Concerning the general applicability of our results, a certain degree of caution should be taken. The heuristic algorithms are fairly general and could be easily adapted to other scenarios of human–robot collaboration, also outside the area of PCB production. The ILP models, on the other hand, are clearly tailored for the specific assembly task. However, in Sections 3 and 4.2, a number of extensions and generalisations were introduced. These should serve as blueprints for the application of our models to other multi-agent production problems. The generality of the computational results is more limited. As crucial influencing factors of performance in general we could identify: (i) similarity or difference of human and robot capabilities, (ii) resolution of the time horizon (i.e. total number of points in time to be considered), (iii) number of tasks to be assigned and scheduled for each workpiece.

7. Conclusion

We considered a human–robot collaboration scenario for a general production planning problem and formulated an ILP model to represent many aspects that are typical for such a collaborative environment. We also formulated a family of heuristic approaches, which can deliver solutions very quickly, but clearly miss optimality. The model and the heuristics were applied to two different production settings in the PCB (printed circuit board) assembly. One setting dealt with the optimal production plan for the tasks required for a single board, the second setting regarded the optimisation of tasks for an entire sequence of different boards, some of which could be processed simultaneously. Since the latter, more complex scenario could not be solved by the ILP model, a matheuristic approach was developed combining the sorting of boards given by a heuristic rule with the (sub-)optimal solutions of subproblems derived by means of an ILP model. Here, each subproblem is a result of the sorting and the solutions of preceding subproblems. Performing experiments on a real-world use case provided by an electronics company, we showed that this matheuristic approach could successfully handle the complex problem, and outperforms the purely heuristic approaches by far. From different ordering variants of the matheuristic considered, the classical ‘longest processing time’ (LPT) rule could be identified as the most promising strategies.

In addition to simply solving a given production scheduling problem, the approaches we introduced can also be used as a decision support tool for the optimisation of the overall production setup, answering questions such as how many human workers and collaborative robots are to be employed or how many workpieces should be processed in parallel. In this case, the runnning time issue is less crucial, since one could pre-compute a larger number of scenarios over time and start the decision making process when all results are available.

For future research, it is interesting to consider the nondeterministic aspect of human nature as a factor in the production process. In this paper we assume that the human workers follow exactly the given work plan and execute each task at the specified time. One may also consider working scenarios where human workers execute more freedom of decision: e.g. they may pick their next task on their own from a set of available tasks or start a task at any time within a certain interval. In such cases, the production planning system may receive on-line input on the current activity of each worker (e.g. via optical sensor techniques) and deploy the robots accordingly.

Mathematically, interesting settings arise if human–robot collaboration is required in the sense that certain tasks have to be performed by several agents together. This situation has been treated in multi-robot or multi-agent planning problems (see Section 2) but the coordination of humans and robots with different individual characteristics brings another level of difficulty to the planning task.

From a technical perspective, it is also interesting to consider sequences of tasks which have to be processed in direct succession of each other without any breaks (e.g. because a work piece should not cool down). Such a production planning problem is known as no-wait scheduling problem. More to the point, one should consider general assembly problems, where only some of the tasks are arranged as strings of successive no-wait operations.

Acknowledgements

We would like to thank Gábor Csapláros from Zollner Elektronik, Vác, Hungary, for providing the technical background and test data specification of our industrial use case.

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

The research is partly funded by the two Austrian research projects CollRob and DeSSnet: (1) This research was funded by the Austrian Ministry for Transport, Innovation and Technology (BMVIT) within the framework of the sponsorship agreement formed for 2015–2018 under the project CollRob. (2) The K-Project DeSSnet was funded within the context of COMET – Competence Centers for Excellent Technologies by the Austrian Ministry for Transport, Innovation and Technology (BMVIT), the Federal Ministry for Digital and Economic Affairs (BMDW), and the federal states of Styria and Carinthia. The programme is conducted by the Austrian Research Promotion Agency (FFG).

Notes

1 www.zollner-electronics.com

2 The selection of the first tasks is done by giving preference to tasks which appear in a larger number of AND- and OR-predecessor sets.

3 www.fico.com/products/fico-xpress-optimization-suite