Truck Scheduling: A Case Study in the Automotive Sector

Abstract

Logistic companies face several problems in their services, leading to increased time and costs in their operations. These issues could be mitigated if decision-making were based on models that consider resource optimization and respect process constraints. An example of this problem is the queues generated by trucks at docks for loading and unloading materials in the automotive sector. Therefore, this work studies truck scheduling with the inclusion of forbidden time windows for breaks. The aim is to propose a mathematical model in order to minimize the time spent by drivers within companies and to present exact and approximate solutions with the use of Operational Research techniques and algorithms. Methods and algorithms that adapt to this type of problem were identified. Then, the mathematical model was developed, computationally implemented in the LINGO and Gurobi software, and validated according to the case study conditions. A metaheuristic based on the Simulated Annealing algorithm was implemented in Visual Basic for Applications language, and used as a form of approximate resolution for problems larger than the ones solved optimally. Computational experiments were conducted to evaluate the performance of the model and metaheuristic proposed. The GAP between the metaheuristic solution and the optimal solution is less than 4% for all problems tested. For larger problems, with more than 10 trucks and 5 docks, Gurobi optimization software is not able to find the optimal solution in a feasible time. However, the metaheuristic is able to find good solutions for bigger problems in a reasonable time. Therefore, results proved the performance of the mathematical model, indicating that truck scheduling is an important tool for automotive companies, as it can help to improve efficiency and productivity.

Introduction

The Production Planning and Control importance is increasing in all environments [5, 12, 41]. The efficient use of human, material and productive resources combined with cost reduction and an increase in customer service quality are key factors to maintain companies’ competitiveness [21, 46].

In order to achieve these objectives, many decision-making processes are involved in the process as a whole, for example, what is the customer service sequence [18], when and how much of each material to buy [29], and the order in which jobs are performed [45], among others. According to [46], sequencing and production scheduling are two of the activities included in the scope of Production Planning and Control.

According to [4], the need for sequencing arises when several items are processed in the same equipment and there is a different preparation for each item. Considering the constraints involved in this sequencing process, the waiting time can have a high impact on the production flow, increasing the processing time and production costs as well. From this scenario, the importance of a good production schedule is highlighted.

Also according to [4], scheduling is not only applied to production, other sectors can also benefit from this activity, such as the logistics sector. One of the applications for this sector is vehicle scheduling. This work will address a more specific vehicle scheduling problem: truck scheduling [48].

The problem scenario involves daily arrivals of several trucks, which need to visit some established docks to unload and/or load materials. The truck schedule seeks to determine the processing order of the trucks at each dock, as well as the time of arrival and departure of the truck at each dock.

This problem was based on an automotive company, where the scheduling activity is performed manually. This company does not use any software to perform the activity, similar to many others, whether or not in the automotive sector. In addition, there is no defined methodology for this scheduling, the employee responsible for this job performs it according to his experience. As a result, long queues of trucks form in the companies’ yards, leading to idle time for drivers and, consequently, generating additional costs for the companies that could be avoided.

Based on what was presented and considering that companies are striving to implement optimization models at each stage of the decision-making process [35], this study aims to generate the best trucks schedule and the sequence of docks to be visited by each vehicle in order to minimize the time spent by drivers within the company. The purpose is to adapt the case study to a sequencing and scheduling problem, more specifically an open shop problem, and propose a mathematical model in order to minimize the time spent by drivers within the company and solve it exactly using optimization software and also solve it through metaheuristic application.

Therefore, the research mathematically modeled a problem that can be faced by any company, not only in the automotive sector. Mathematical modeling can be applied to any company that has jobs (trucks, in the context of this research) to be processed on predefined machines (docks, in the context of this research), where some machines need to perform their activities before others (unloading before loading, in the context of this research), and some machines need to stay inactive for a certain period (forbidden time windows representing periods when docks cannot receive trucks, in the context of this research). For large-scale problems, the Simulated Annealing metaheuristic is proposed to find an approximate solution to the problem, whereas the NEH heuristic was adapted to our problem to generate initial solutions for the metaheuristic. Therefore, the main contribution of this research is to provide a tool for companies in the manufacturing sector that have their machines inactive during a certain period of time and wish to perform efficient sequencing and scheduling of their jobs.

This paper is organized as follows: Sect. 2 presents a literature review of the main topics used in this study. Section 3 proposes a mathematical formulation for the problem based on an open shop scheduling problem. A metaheuristic approach is presented in Sect. 4. Section 5 covers the computational results. Finally, Sect. 6 presents the conclusions and future work.

Literature Review

A brief theoretical framework for the research problem is presented in this section. Initially, fundamental concepts of Industrial Engineering and operational research tools are presented, in order to seek theoretical support to solve the question: Given a set of trucks arriving at the facilities to be processed in a specific set of docks, which truck should go to which dock, in what sequence, and at what time, considering that some docks are inactive at certain times?

Production Planning and Control

Production Planning and Control (PPC) is classified as a support sector that analyzes information from different areas in order to manage productive resources and operations [21, 34, 43]. Its functions are master production schedule, demand management, material and capacity requirements planning, and job scheduling and sequencing [10].

PPC aims to produce, with the minimum cost, what the market demands in the expected time and with the expected quality [10]. However, various other objectives can be requested in PPC, [21] lists some: minimize the idle times of men and machines, minimize inventory turnover, minimize bottlenecks along the production flow, keep inventory levels low, maximize customer satisfaction, provide low setup times, etc.

According to [46], PPC seeks to reconcile supply and demand in terms of volume, time and quality, and this involves three activities:

• Loading: refers to the volume allowed for a productive operation;

• Sequencing: establishes the priority of jobs to be performed;

• Scheduling: specifies the start and end times for each job. This activity is one of the most complex in Production Planning and Control, as the number of possible schedules grows rapidly due to the number of activities and processes.

Production planning is one of the key elements of a company’s production program and ensures that all materials and production components are available [35]. For example, in the automotive sector, it is crucial that parts are always available when required in the manufacturing of a vehicle. Boysen et al. [8] describe the elementary stages of the parts logistics process in the automotive industry and conduct a literature review on the decision problems faced in the sector. The authors conclude that, despite the significant importance of parts logistics in the automotive industry and the encompassing of many challenging optimization problems, the literature is scarce regarding decision problems.

According to [40], an inefficient supply chain limits the evolution of the automotive sector in some countries. In this regard, [50] state that trucks transporting parts to assembly factories need to be processed quickly at the factory facilities to ensure smooth operations, improve supply chain performance, and avoid delays and demurrages.

Truck Scheduling

Trucks and docks management can be a very complex activity, as according to [24], managers seek to meet supplier requirements regarding arrival and departure times in the industry, in order to improve the relationship with all stakeholders involved.

According to [25], trucks and docks management can be categorized into three different problems:

• Truck assignment: the number of trucks is generally less than the number of docks. It seeks to define which truck will be assigned to which dock and it considers only the spatial dimension;

• Truck sequencing: the number of trucks is greater than the number of docks and the objective is to determine the trucks processing order at each dock;

• Truck scheduling: incorporating the temporal dimension in the sequencing problem. In addition to the order, the time of arrival and departure of the trucks at each dock is also defined.

The problem of managing trucks and docks is complex, depending on the constraints and the size of the problem. Boysen et al. [8] report that in Germany, a major automobile producer faces daily local traffic of up to 500 trucks at its 70 unloading docks.

Berghman et al. [6] present a situation in a Toyota warehouse in Belgium. The problem involves trailers that arrive at a warehouse and need to unload their products and trailers that need to load products before leaving the warehouse. The goal is to minimize the delivery time for the logistics operators of these trailers. The problem was modeled as a flexible 3-stage flow shop. The authors considered a fixed transportation time, regardless of distance, and proposed three different integer formulations to be applied to the Toyota problem. The formulations were based on designation, flow and indexing time.

Cota et al. [11] present a two-stage sequencing problem, for incoming trucks and outgoing trucks, with the objective of minimizing the makespan. The authors modeled the problem as a two-stage hybrid flow shop with the presentation of a mixed integer linear formulation with indexing time. They tested a constructive polynomial heuristic for solving medium and large instances.

A scheduling problem in which trucks need to visit some specific docks to deliver parts is addressed in [50]. Each truck has an individual arrival time and forecast to leave the factory. The objective is to minimize the penalty for trucks that do not respect the leaving time of the factory. The authors proposed a mixed linear programming model based on the open shop problem for solving small problems and used the metaheuristic known as the Greedy Randomized Adaptive Search Procedure.

Tadumadze and Emde [47] investigate the operational planning problem of loading and scheduling outbound trucks in a shipping warehouse. Shipping warehouses of automotive parts manufacturers that supply parts to equipment manufacturers in a just-in-time or even just-in-sequence manner are examples of this type of planning problem. Thus, the processing of trucks at docks is scheduled without exceeding available resource levels (logistics workers and dock doors, for example), and time windows are considered. A mixed-integer linear programming model indexed in time is developed and solved exactly.

Truck scheduling problems in the context of cross-docking are addressed in various studies but can be complex, according to [51], as they involve the number and type of docks, the number and type of trucks, truck arrival times, and the number and characteristics of products.

A state-of-the-art review with a particular focus on the truck scheduling problem in cross-docking terminals is conducted in the study by [48] The authors conclude, based on the literature, that most studies assume the exclusive dock assignment mode throughout the truck scheduling, and few studies consider preemption, where a given truck is allowed unloading or loading some of its products, leaving the dock for other trucks, and returning later to complete its service. It is also concluded that the primary objective aimed for is the minimization of truck service time in the mathematical formulation, and the majority of studies propose metaheuristic algorithms for problem resolution.

Open Shop

Sequencing and scheduling problems are usually based on the number of jobs, number of machines and job processing routes. The sequencing and scheduling problems most cited in the literature are the flow shop [26, 49] and the job shop [52, 53].

There is a third scheduling problem, less known than the two mentioned above, called the open shop [23]. According to [31], this problem is applied to cases in which the processing routes are not previously determined.

Considering n jobs and m machines, each job has to be processed on each of the m machines. According to [36], the main differences of the open shop are:

• The processing time on some machines can be zero;

• Job processing routes are open. Besides the job sequence decision on each machine, the problem also has the objective of deciding the route processing for the jobs.

Ahmadian et al. [2] consider four decades to conduct a literature review on the open shop scheduling problem to minimize makespan. They report a wide range of applications, such as timetabling, satellite communication, health care management, tourism, and transport.

In the transportation sector, truck scheduling stands out. Cankaya et al. [9] present a practical study on the scheduling of chemical tanker ships visiting the port of Houston, which often need to wait long periods to load and unload their products. The extended waiting times result in unnecessary movements that increase the business costs for shipowners, risk of collisions and allisions, production of additional air emissions, and decrease the operating capacity of terminals.

Gholami et al. [17] explore scheduling trucks in fruit cross docks as an open shop problem to minimize the unloading time of the inbound trucks, thereby avoiding expenses related to cooling and food deterioration.

Due to the complexity of the open shop problem in real-life situations with many variables and constraints, most mathematically modeled problems cannot be solved exactly in a timely manner. Therefore, heuristics and metaheuristics are required to find an approximate solution to the problem [3].

NEH Heuristic

The NEH heuristic was proposed by [32] to obtain solutions for the permutational flow shop scheduling problem, which assigns high priority to jobs with high total processing times [28].

According to [44], the heuristic consists of two phases. In the first phase, jobs are ordered according to non-decreasing sums of processing times. The second phase involves constructing the solution sequence, where gradually all jobs from the initial solution are examined in all possible positions in partial sequences, choosing the one that guarantees the lowest total scheduling time.

The steps proposed by [32] are:

1. For each job, sum the processing times on all machines to be visited;

2. Sort the jobs from the longest sum of processing times to the shortest;

3. Select the first two jobs and find the best sequence by calculating the objective function;

4. Select the next job from step 2 and find the best position to insert this job in the sequence found in step 3.

Due to its simplicity and good results, the NEH algorithm is the most popular construction heuristic for the flow shop scheduling problem [38], but its easy adaptation to similar problems have led to its application to other scheduling decisions [13]. Prata et al. [37] conducted a bibliometric analysis of the NEH algorithm, spanning from its inception in 1983. The authors conclude that the vast majority of scientific research utilizes NEH in the permutation flow shop and job shop. However, the adapted heuristic is also employed in other production scheduling problems, citing the open shop problem.

In this sense, [54] propose a hybrid method to solve the open shop problem in which the NEH heuristic is used to find the initial solution of the problem to the sequencing of operations of a set of jobs on a set of machines.

Jananeeswari et al. [20] solve an open shop scheduling where the job once started should have continuous processing through the machines without the wait. They use the idea that the arrangement of jobs is executed in the reverse order of the NEH algorithm.

Abreu et al. [1] adapt the constructive heuristic NEH for an efficient generation of the initial solution for open shop scheduling with routing by capacitated vehicles.

Simulated Annealing Metaheuristic

Simulated Annealing was initially proposed on [22] and is based on the metals cooling and recrystallizing physical process presented by [30].

In the physical cooling model proposed by [30], the system starts with a high temperature. High temperatures cause a high level of atoms disorder, which can move freely, and consequently increase the system energy. As the temperature decreases, the system reaches states more orderly and with lower energy, until it reaches the equilibrium state, with minimum energy. In the metaheuristic, the objective function is represented by energy, changes in the state represent the solutions obtained from the neighborhood of the problem initially proposed, and the minimum energy state represents the optimal solution [39].

The metaheuristic starts with a random solution and a high temperature parameter. At each iteration, a new configuration is generated from the initial solution neighborhood and the adoption of this configuration as a new solution is based on a probabilistic decision. At each iteration, the temperature parameter is reduced in value. According to [33], the algorithm steps are:

1. Choose an initial solution to start off the optimization process;

2. Select a generation mechanism to make a transition from a configuration to another one by a small perturbation;

3. Evaluate performance measure;

4. Accept the new configuration if there is an improvement; otherwise, probabilistically accept (or reject) it;

5. According to stopping rules, either stop or continue iterations at step 2.

According to [14], the acceptance of worse solutions is a differential of the Simulated Annealing algorithm, since this characteristic allows the algorithm to move from the local area of exploration to other neighborhoods with potential for better solutions, avoiding the search to be restricted to only one location.

Gallo and Capozzi [16] employ Simulated Annealing to solve a task scheduling problem in discrete and continuous domains. The authors propose a randomization of the metaheuristic, and the experimental results show that it provides an improvement in performance in terms of better solutions and runtime when compared to task scheduling and Simulated Annealing as independent algorithms.

In the context of our research, [27] adopted Simulated Annealing to solve the problem of assigning trucks to docks. The authors present some methods of generating new solutions based on uniform mutation operators, by random numbers generation.

Shahmardan and Sajadieh [42] address the truck scheduling problem in a cross-docking center where a dock door can be assigned to both outbound and compound trucks, and furthermore, trucks can be partially unloaded. To solve the problem in an approximate manner, the authors use reinforcement learning-based Simulated Annealing approaches.

Wu et al. [51] consider a cross-docking system without temporary storage for the truck scheduling problem, where the total operation time is minimized. The Simulated Annealing metaheuristic is employed to find an approximate solution to the problem, along with particle swarm optimization and variable neighborhood search metaheuristics. Computational tests show that all three approaches can achieve very good solutions, even in large-scale problems.

Problem Description and Mathematical Model

The problem addressed in this work is based on automotive company operations, located in southern Brazil, more specifically the vehicles scheduling for loading and unloading activities in an the industrial complex. Every day, the company receives several trucks that go through some docks to unload materials. Some trucks, after unloading all the materials, go through some docks to collect packages from previous visits. The company already knows which docks must be visited by each truck according to the supplier and the materials to be delivered.

In addition, the operating docks of this automotive company have different working hours. The docks are gathered into larger groups according to the production process, and each group of docks operates on different shifts, resulting in different starting and closing times, as well as different break times.

This scenario of different operating hours and different break intervals is very common in sequencing and scheduling problems. Therefore, the modeling should consider forbidden time windows in order to propose a comprehensive mathematical model applicable to different companies and situations. An example of the forbidden time window is when maintenance is performed on equipment at the dock (gates, lifts, ramps, levelers, sensors, etc). Thus, forbidden time windows indicate defined start and end time intervals during which the docks are non-operational and are determined by the company.

The studied company adopts some simplifications in the current scheduling process, one of which is the set of predefined values for the driving times between docks and for material loading and unloading processing times. However, these times are unlikely to be the same for all trucks in real operations, since there are several variables that can influence them, such as truck type and goods characteristics. As this work aims to reflect the real operations conditions, and considering the objective to propose a model that can be easily replicated by other companies, the processing times simplification will not be adopted in this paper.

Two other points observed in the operations of this automotive company will be replicated in the mathematical model. The first one is a condition imposed on trucks to load and unload materials. In these cases, the company imposes a constraint that before starting the loading process, the truck must have already unloaded materials in all scheduled docks.

Other information to be considered in the mathematical model is that before starting the journey through the docks, each truck must pass through the reception to perform some administrative activities such as registration of the driver, truck and goods data, and time of the truck’s entry into the company, among other information.

The mathematical model presented next is based on [31, 50]. These references were chosen as a basis due to their similarity to the case study used in this research, which involves the mathematical modeling of an open shop problem to determine the processing routes for each job (truck) on each machine (dock). The mathematical modeling proposed in this paper was inspired by and adapted for the case study from the two references mentioned earlier.

Now, we present the variables, parameters and constraints applied to the proposed mathematical model.

The indices below were the ones applied to variables and parameters:

j, k: truck indices $\{1,2,...,n\}$;

i, l: dock indices $\{0,1,2,...,m\}$;

v: forbidden time window indices.

The index $i=0$ represents the dummy dock, which has processing times equal to zero. This dock is applied to the problem formulation to ensure all variables are correctly calculated. The reception was also defined as a dock $(i=1)$.

The parameters used in the formulation are defined below:

n: number of trucks;

m: number of docks;

b: number of forbidden time windows;

$p_{j,i}$: processing time of truck j in dock i;

$O_{j,i}$: operation type of truck j in dock i;

$d_{l,i}$: driving time from dock l to dock i;

$f{w}_{i,v}$: beginning of forbidden time window v in dock i;

$df{w}_{i,v}$: duration of forbidden time window v in dock i.

The possible values of $O_{j,i}$ are 0, 1, 2 and 3. The parameter will be equal to 0 when truck j does not visit dock i. The value 1 indicates the service at reception. Values 2 and 3 represent unloading and loading operations, respectively.

The variables are presented below:

$X_{j,i,l}=\left\{\begin{array}{cc}1,& \text{if truck}j\text{is designated to dock}i\text{after operation in dock}l;\hfill \\ 0,& \text{otherwise.}\hfill \end{array}\right)$

$Y_{j,i,k}=\left\{\begin{array}{cc}1,& \text{if truck}j\text{is designated after truck}k\text{in dock}i;\hfill \\ 0,& \text{otherwise.}\hfill \end{array}\right)$

$Z_{j,i,v}=\left\{\begin{array}{cc}1,& \text{if truck}j\text{in dock}i\text{is designated after forbidden time window}v;\hfill \\ 0,& \text{otherwise.}\hfill \end{array}\right)$

$C_{i,j}$: completion time of truck’s j operation in dock i;

$T_j$: completion time of truck j;

$S_j$: starting time of truck j;

$D_{j,i,l}$: driving time from dock l to dock i for truck j.

The problem can be formulated as follows:

1

$$\begin{array}{c}\hfill min\sum _{j=1}^n{T}_j\end{array}$$Subject to:

2

$$\begin{array}{cc}\hfill & Y_{j,i,k}+Y_{k,i,j}\le 1\forall i,j,k\ne j\hfill \end{array}$$

3

$$\begin{array}{cc}\hfill & X_{j,i,l}+X_{j,l,i}\le 1\forall j,i,l\ne i\hfill \end{array}$$

4

$$\begin{array}{cc}\hfill & X_{j,i,l}=0\forall j,i,l\ne i\mid O_{j,l}>O_{j,i}\hfill \end{array}$$

5

$$\begin{array}{cc}\hfill & C_{j,0}=0\forall j\hfill \end{array}$$

6

$$\begin{array}{cc}\hfill & S_j=C_{j,1}-p_{j,1}\forall j\hfill \end{array}$$

7

$$\begin{array}{cc}\hfill & D_{j,i,l}=0\forall j,i,l\mid p_{j,i}=0\hfill \end{array}$$

8

$$\begin{array}{cc}\hfill & D_{j,i,l}=d_{l,i}\forall j,i,l\mid p_{j,i}\ne 0\hfill \end{array}$$

9

$$\begin{array}{cc}\hfill & C_{j,i}\ge C_{j,l}+p_{j,i}+D_{j,i,l}-M\ast (1-X_{j,i,l})\forall j,i,l\ne i\hfill \end{array}$$

10

$$\begin{array}{cc}\hfill & C_{j,i}\ge C_{j,l}+p_{j,l}+D_{j,i,l}-M\ast X_{j,i,l}\forall j,i,l\ne i\hfill \end{array}$$

11

$$\begin{array}{cc}\hfill & C_{j,i}\ge C_{k,i}+p_{j,i}-M\ast (1-Y_{j,i,k})\forall i,j,k\ne j\hfill \end{array}$$

12

$$\begin{array}{cc}\hfill & C_{k,i}\ge C_{j,i}+p_{k,i}-M\ast Y_{j,i,k}\forall i,j,k\ne j\hfill \end{array}$$

13

$$\begin{array}{cc}\hfill & C_{j,i}-f{w}_{i,v}-df{w}_{i,v}+M\ast (1-Z_{j,i,v})\ge p_{j,i}\forall j,i,v\hfill \end{array}$$

14

$$\begin{array}{cc}\hfill & f{w}_{i,v}+M\ast Z_{j,i,v}\ge C_{j,i}\forall j,i,v\hfill \end{array}$$

15

$$\begin{array}{cc}\hfill & T_j\ge C_{j,i}\forall j,i\hfill \end{array}$$

16

$$\begin{array}{cc}\hfill & X_{j,i,l}\in \{0,1\}\forall j,i,l\ne i\hfill \end{array}$$

17

$$\begin{array}{cc}\hfill & Y_{j,i,k}\in \{0,1\}\forall i,j,k\ne j\hfill \end{array}$$

18

$$\begin{array}{cc}\hfill & Z_{j,i,v}\in \{0,1\}\forall j,i,v\hfill \end{array}$$The objective 1 is to minimize the sum of the time spent by the trucks to carry out their operations at all docks.

Constraints 2 state that, for any dock i, a truck cannot be the successor and predecessor of another truck at the same time. Constraints 3 have the same purpose as Constraints 2 but are focused on docks sequencing, for any truck j, a dock cannot be the successor and predecessor of another dock at the same time.

Constraints 4 force the reception and docks that have processing time equal to zero to be visited before the other docks; they also ensure the assignment of a dock that receives an unloading operation before the assignment of a dock that receives a loading operation.

Constraints 5 determine that the completion time for all trucks will always be 0 at dock 0, which represents a dummy dock. This dummy dock seeks to ensure that the completion times of each truck at each dock are calculated correctly, respecting the completion times of previous positions, as well as the processing time of the current position.

Constraints 6 determine trucks arrival time. Considering that the reception (dock 1) should be the first dock to be visited by all trucks, it was determined that the arrival time of each truck will be the completion time at dock 1 minus the processing time for this dock. This decision was made with the purpose of ensuring that when a truck arrives at the company, it will go straight to the reception desk, avoiding a waiting time in this initial stage.

Constraints 7 and 8 redefine the driving time among docks in order to ensure that it will not be considered in cases where there is no operation to be carried out at the dock. When a truck j has a processing time equal to zero at dock i$(p_{j,i}=0)$, no operations are performed at this dock, so there is no need for the truck to drive to dock i. In this case, driving times from all other docks to dock i will be considered equal to zero for truck j. For docks where trucks carry out a loading or unloading operation, driving times remain the same as those predefined in the parameter $d_{l,i}$.

Constraints 9 and 10 are disjunctive constraints and seek to ensure that for each truck j, dock i is designated after dock l, or dock l is designated after dock i. Constraints also ensure that the truck will only move to the next dock after completing the activity at the previous one. This will prevent an operation on a given dock from being interrupted during its execution to go to another dock, and later, having to return to the dock that had the operation interrupted.

Constraints 11 and 12 are also disjunctive and ensure that a dock will receive the next truck only after the completion of the previous truck’s operations.

Constraints 13 and 14 deal with forbidden time windows and seek to ensure that no trucks will be assigned to start operations on a dock during forbidden time windows, as well as to ensure that truck operations end before forbidden time windows start, which are time intervals in which the docks are inoperative.

Constraints 15 calculate the total completion time of each truck. Trucks completion times at docks are cumulative, which means the completion time of the second dock of the sequence for a given truck will consider the completion time of the first dock adding the processing time of the second dock, and so on. With that, it can be concluded that the truck completion time will be the maximum value among the completion times of all docks designated for that truck. Constraints 16–18 define the variables types (binary).

As the problem was modeled, it is not possible for two or more trucks to arrive at the same dock simultaneously, nor for trucks to overtake each other upon arrival at a dock, as the sequencing and scheduling of each vehicle are performed, consequently without conflict of arrivals. However, what can occur is the crossing of truck routes while they circulate in the company’s yard toward the docks.

Approximate Solution

This section aims to present the proposed algorithm based on the Simulated Annealing metaheuristic, as well as its parameters, to approximately solve the mathematically modeled problem in this research. This metaheuristic was chosen because it is one of the most employed techniques in open shop problems, either in its original form or in a hybrid manner [3].

Proposed Algorithm

Now, we present the adaptation of the Simulated Annealing (SA) algorithm to the open shop problem proposed in this work. Figure 1 shows a flowchart of the proposed algorithm.

[See PDF for image]

Fig. 1

Flowchart of the proposed SA algorithm

The algorithm starts with the generation of the initial solution (S) followed by the objective function/energy calculation (f(S)). The initial temperature (T) is also defined before initiating the neighborhood search.

Once the input parameters such as the initial solution and the initial temperature are defined, the next steps are run until the stop criteria is reached:

• Generate a new solution ($S^{\prime }$) as a result of a disorder in the initial neighborhood (disorder methods $D{M}_i$$(i=1,...,5)$ will be discussed in Sect. 4.4);

• Calculation of objective function for new solution ($f(S^{\prime })$);

• Energy variation calculation ($\mathrm{\Delta }E$);

• If the variation is negative, it means an improvement in the objective function, therefore the new solution replaces the initial one;

• If the variation is positive, the new solution acceptance is based on Boltzmann-Gibbs factor: $p(\mathrm{\Delta }E)=e^{-\mathrm{\Delta }E/T}$;

• Temperature reduction based on the temperature reduction factor ($\alpha$).

Next subsections will provide more details on the steps and parameters definition.

Initial Solution

One of the input parameters for the Simulated Annealing algorithm is the initial solution, and in this case, it is the designation and sequencing of the trucks to the docks. The method used to generate the initial solution was based on the NEH heuristic proposed by [32], such that the prioritization in the assigning jobs (trucks in the context of this work) process must be proportional to the sum of the processing times in the machines (docks).

The optimal solutions generated by LINGO and Gurobi were also analyzed in order to identify patterns that could be replicated in the generation of the solution. It was observed that the designation always started with the truck that had the shortest processing time at dock 1, which represents the reception and is the first dock to be visited by each truck. This observation was included as a step of the proposed initial solution method. Based on this optimal solutions observation and the NEH heuristic presented in Sect. 2.4, the method proposed in this work to obtain the initial solution follows the following steps:

• Determine the truck that has the shortest processing time at dock 1 and include it in the first position of the truck sequence Sc. If two or more trucks have the same processing time, the first analyzed truck is considered;

• For the other trucks, sum the processing times at all docks to be visited by each truck;

• Sort trucks from the smallest sum of processing times to the longest. Include this ordering in the sequence of trucks (Sc), starting from position 2, since position 1 was already determined in the previous step;

• For each truck, sort the docks to be visited according to the constraints of the problem, generating a sequence (Sd) of docks to be visited for each truck. The dock that represents the reception should be the first one to be visited, followed by the docks where unloading operations are carried out. The route ends with the docks where loading operations are executed.

The final result of this stage should be the sequence of docks to be visited by each truck. The information obtained from the steps presented above is structured in a matrix named Order. Since n is the number of trucks and m is the number of docks, the initial solution matrix has n rows and $m+1$ columns. The first column of the matrix will inform the ordered sequence of trucks (Sc). The sequence of docks to be visited by each truck will be available in each row, from columns 2 to $m+1$. It should be noted that even if the processing time in a given dock is zero, that dock will still be related in the matrix Order.

Objective Function–Energy Calculation

The methodology to be applied for the energy calculation is another factor to be defined before executing the metaheuristic. The energy is the objective function of each configuration generated during the algorithm execution.

Considering that the designation and sequencing of the trucks to the docks has already been completed, the next step is the scheduling of the trucks to the docks, which consists in determining the start and ending time of each truck in each dock. After calculating all these times, this step ends with the objective function calculation, which is the sum of the completion times at the last visited dock by each truck. The main input parameter for this step is the Order matrix generated in the previous step, containing the sequence of trucks in the first column and the sequence of docks to be visited by each truck in the rest of the matrix.

The programming process starts with the first truck in the ordered sequence (Sc), in other words, the first line of the first column of the Order matrix. The process begins with the completion time calculation of this truck at the first dock to be visited, which is found in row 1 and column 2 of the Order matrix. The completion time calculation follows to the next dock, which is the value of row 1 and column 3 of the matrix, and so on, up to column $m+1$. Dock completion time calculations take into account the forbidden time windows on each dock and ensure that there are no operations on the docks during these breaks.

The completion time calculation at each dock follows some steps in order to determine the time when the dock and the truck are available to start the operation.

The first step is to check if the dock is the first one to be visited by the truck. If so, the completion time of the truck previously assigned to this dock is determined. This instant becomes the new availability moment for the current truck and dock. If the dock is not the first one to be visited, the completion time at the last dock visited by the truck is checked and the driving time from the previous dock to the current one is added, the result is considered as the new availability.

This new availability is then compared to the completion time of the last truck that visited the current dock. If the ending time for this truck is longer than the availability previously calculated, this time becomes the new availability for the current dock and truck.

Finally, availability is compared to the current dock break times. If the dock availability moment is between the beginning and the end of the forbidden time window, or if the operation execution period conflicts with the forbidden window, the truck availability in the current dock becomes the end of the forbidden time window.

Once all docks on the first truck have been scheduled, the next truck to be analyzed is the one located in the second row and first column of the Order matrix, and so on, until the last truck in the matrix is analyzed.

After all completion times are calculated, the total ending time for each truck is determined, which is the completion time of the last dock visited by each truck. This step ends with the objective function calculation, which is the sum of the total completion times of all trucks.

Disorder Methods

According to [14], Simulated Annealing is a stochastic local search algorithm, which means the algorithm starts with an initial solution, randomly generated, and at each iteration, the initial solution neighborhood is explored in order to determine a new solution. The new solution is usually obtained from a disorder in the initial solution.

The exploration methods in the neighborhood depend on the nature of the problem being solved. In this work, 5 disorder methods have been proposed based on the works [15, 27], and all methods consider the Order matrix generated in the previous step as the basis. Considering the precedence constraints between the docks in relation to the type of operation performed at the docks (docks where unloading operations are carried out, must be visited before the docks where loading operations are carried out), the disorders in the docks sequence to be visited by each truck (changes in the matrix columns) become more difficult. Therefore, the disorder methods seek to generate new solutions through the truck’s reorganization (changes in the matrix lines).

The first method ($D{M}_1$) randomly selects two numbers, which represent two lines of the Order matrix, and consequently two trucks, and switches the lines between them.

Figure 2 shows an example with 7 trucks and 5 docks, the first column shows the order of the trucks. The designation starts at the first line, with truck 5. This truck starts its route at dock 4, followed by dock 5, and so on until it ends at dock 2. By method $D{M}_1$, two random numbers, 3 and 6, were selected and these lines were exchanged with each other, which means line 6 becomes line 3 and vice versa.

[See PDF for image]

Fig. 2

Example of the disorder method $D{M}_1$, in which the numbers 3 and 6 were drawn

The second method ($D{M}_2$) generates a random number, representing a line in Order matrix. This disorder exchanges the selected line with the line immediately afterward. Figure 3 shows an example, in which the number 5 was randomly generated.

[See PDF for image]

Fig. 3

Example of the disorder method $D{M}_2$, in which the number 5 was drawn

The third method ($D{M}_3$) generates two random numbers, in order to form a subsequence between the lines of the Order matrix, then the order of the trucks in this subsequence is reversed. In the example of Fig. 4, numbers 1 and 5 were generated, forming the subsequence of lines 1 to 5 of the matrix. Applying this method, line 5 becomes line 1 and line 1 becomes line 5; line 4 becomes line 2 and line 2 becomes line 4; and so on, until the entire subsequence is reversed.

[See PDF for image]

Fig. 4

Example of the disorder method $D{M}_3$, in which the numbers 1 and 5 were drawn

The fourth method ($D{M}_4$) selects two random numbers and removes the first line from the sequence and inserts it in the second selected position, as shown in Fig. 5, where numbers 1 and 6 were selected.

[See PDF for image]

Fig. 5

Example of the disorder method $D{M}_4$, in which the numbers 1 and 6 were drawn

The last disorder method ($D{M}_5$) proposed focuses on the sequence of docks visited by trucks and seeks to propose a new sequence in order to continue to meet visits to docks constraints. This method selects a random number (truck). If the truck has, for example, more than two unloading activities, two of these docks are randomly selected and the visit order between them is reversed. The same logic is applied to loading activities. Table 1 shows the operations that each truck (T) executes in each dock (D) for a problem with 5 docks and 7 trucks. Values 1, 2 and 3 indicate, respectively, reception services, unloading operations and loading operations. Value 0 indicates the truck does not need to visit the dock.

Table 1. Types of truck operation at the docks–7 trucks and 5 docks

Truck	Dock
	D1	D2	D3	D4	D5
T1	1	3	0	2	0
T2	1	2	2	3	0
T3	1	0	3	2	0
T4	1	2	3	0	0
T5	1	3	2	0	0
T6	1	0	3	2	0
T7	1	2	3	0	0

In Fig. 6, the number 7 was selected as an example, corresponding to truck 2. Analyzing data in Table 1, truck 2 executes two unloading operations in docks 2 and 3, and a loading operation in dock 4. Analyzing the data displayed on the left side of Fig. 6, dock 2 is visited before dock 3. The $D{M}_5$ method application will reverse the order of visits to these docks. After dock 1, the truck would go to dock 3, drive to dock 2 and it would finish the route in dock 4.

[See PDF for image]

Fig. 6

Example of the disorder method $D{M}_5$, in which the number 7 was drawn

The choice of the disorder method to be used in each iteration is made in a probabilistic way by drawing a number between 0 and 1. The methods were segregated at intervals between 0 and 1 to allow the same chosen probability for each method. If the number drawn is between 0 (inclusive) and 0.2, the $D{M}_1$ method will be chosen; between 0.2 (inclusive) and 0.4, the $D{M}_2$ method is chosen; between 0.4 (inclusive) and 0.6, the $D{M}_3$ method is chosen; between 0.6 (inclusive) and 0.8, the $D{M}_4$ method, and between 0.8 (inclusive) and 1 (inclusive), the $D{M}_5$ method is used.

Other Criteria

The algorithm execution requires other parameters definition, such as initial temperature, temperature reduction factor and stop criteria.

According to [14], the initial temperature must be proportional to the objective function of the initial solution found for the problem in question. In this way, the initial temperature is defined as 1000 times greater than the objective function value for the initial solution ($T=f(S)\ast 1000$). The temperature reduction factor was set at $\alpha =0.99$ according to the authors’ guidelines that the values must be greater than 0.9. The last factor to be decided is the stop criteria. For this work, it was defined as the minimum temperature range, pre-defined as 0.001.

Summary of Metaheuristic Parameters

An important aspect of applying a method is the appropriate selection of its parameters. This section aims to synthesize information regarding the initialization parameters for the Simulated Annealing metaheuristic applied to solve the truck scheduling problem:

• Initial solution (designation and sequencing of the trucks to the docks): method proposed in Sect. 4.2, which was based on the NEH heuristic;

• Initial temperature: 1000 times the value of the objective function;

• Temperature reduction factor at each iteration: 0.99.

The temperature-related parameters (the last two) were chosen according to [14] suggestions.

The objective function for the proposed problem consists of the sum of the completion time at the last visited dock for each truck.

It is known that the Simulated Annealing metaheuristic is sensitive to initial parameters [19]. In this research, a study on how initial parameters affect the solution quality was not conducted. All results presented subsequently using the Simulated Annealing metaheuristic were executed with the parameters provided in this section.

Results

This section presents the exact model results, values obtained by the LINGO (version 18.0) and the Gurobi (version 9.1.0) software, to illustrate the observance of the proposed model to the imposed constraints, in addition to presenting a comparison of computational performance between the two software. The computational tests were carried out on a notebook, with Intel Core i7-6500U (2.50GHz), RAM 16GB, in a Microsoft Windows operating system.

Results obtained by the proposed Simulated Annealing metaheuristic are also presented, as well as the comparison between these results with the exact model results, both objective function values and execution times, in order to analyze the effectiveness of the proposed metaheuristic.

It is important to highlight that in the mathematical model presented in Sect. 3, a dummy dock was considered in order to guarantee the correct calculation of all variables, but in the following results, it will be omitted. Thus, no operation is performed on this dock and the displacement time from any dock to it is 0.

The first set of data tested considers 5 trucks and 4 docks, with a dock representing the reception (dock 1).

The problem data was randomly generated using the Excel random function. The truck operations (represented by the letter T) at the docks (represented by the letter D) have processing times illustrated in Table 2, in time units. Processing times with a value 0 indicate the truck does not perform any operations at the dock. The driving times among docks are shown in Table 3.

Table 2. Processing times (time units)–5 trucks and 4 docks

Truck	Dock
	D1	D2	D3	D4
T1	4	21	0	19
T2	20	19	28	10
T3	23	0	20	3
T4	29	22	9	0
T5	15	22	6	0

Table 3. Driving times (time units) among the 4 docks

Dock	D1	D2	D3	D4
D1	0	8	5	4
D2	8	0	4	3
D3	5	4	0	10
D4	4	3	10	0

The operations types of each truck at each dock are available in Table 4. The value 0 indicates the cases in which the truck does not visit the dock. The value 1 represents the service at the reception. And values 2 and 3 indicate truck unloading and loading operations, respectively.

Table 4. Types of truck operations at the docks–5 trucks and 4 docks

Truck	Dock
	D1	D2	D3	D4
T1	1	3	0	2
T2	1	2	2	3
T3	1	0	3	2
T4	1	2	2	0
T5	1	3	2	0

The problem also considers forbidden time windows. It has been simulated that docks 2 and 3 each have two forbidden time windows each. Dock 2 starts the first forbidden time window at moment 55 and the second window starts at moment 95. Dock 3 also has two forbidden time windows starting at moments 45 and 120. The duration has been set to 5 time units for all forbidden time windows.

Gantt charts were drawn with the trucks sequencing at docks as well as the start and end of operations for each truck at each dock. Each line on the vertical axis represents a dock and the horizontal axis represents instants of time. Each colored rectangle with a code inside (Tj), indicates an operation of the truck j. The colored rectangles without a truck reference code and with smaller heights represent the waiting times of the trucks, that is, the time from which the trucks arrive at the dock until the time to start their operations. Forbidden time windows are represented in black color, each lasting 5 time units. Figure 7 shows the optimal solution and Fig. 8 shows the metaheuristic solution.

[See PDF for image]

Fig. 7

Optimal solution represented by Gantt chart–5 trucks and 4 docks

[See PDF for image]

Fig. 8

Metaheuristic solution represented by Gantt chart - 5 trucks and 4 docks

It is possible to see in Figs. 7 and 8 that the metaheuristic solution was very similar to the optimal solution. The biggest difference is related to the sequence of trucks 1 and 5. While the optimal solution scheduling started with truck 1, the metaheuristic solution starts with truck 5, changing positions with truck 1 when compared to the optimal solution. The other trucks maintained the same positions in the dock schedule sequences.

All trucks start their routes at the reception (dock 1) and the docking schedule respects the constraint that docks receiving unloading operations are designated before docks carrying out loading operations. Observing, for example, the dock schedule for truck 5, it is possible to observe that dock 1 is the first one to be visited by the truck. Then, the truck moves to dock 3 (unloading operation) and ends its route at dock 2 (loading operation) at moment 82 (Fig. 7) in the optimal solution, and at moment 53 (Fig. 8) in the metaheuristic solution.

Evaluating the route of truck 2, it is possible to verify that the driving times and availability of trucks and docks are also respected and considered for the ending times calculation. In the optimal solution (Fig. 7), truck 2 finishes operation in dock 1 at moment 62, and the next dock to be visited is dock 3. The driving time between docks 1 and 3 is 5 units of time, making truck 2 available to start its operations at dock 3 at moment 67. However, at this moment, dock 3 is occupied with truck 3, which ends its operations at moment 76; only when truck 2 can start its activities. The same behavior for this truck is observed in Fig. 8 to the metaheuristic solution.

Forbidden time window constraints are also respected by the model. Looking for example in Fig. 7, truck 5 finishes its operation at dock 1 at time 42, spends 5 time units to move to dock 3 and needs to wait more 2 time units because of the forbidden time window, only then to start its operation at dock 3 at instant 60.

The operations total completion moment of each truck is shown in Table 5 for both solutions. These values represent the completion moment of the last dock assigned to the truck. The objective function for this problem is 498 (optimal solution), representing the total time spent by all trucks to carry out their loading and unloading operations at the docks. The SA metaheuristic solution is 503.

Table 5. Ending time of last designated dock–5 trucks and 4 docks

Truck	Ending time	Ending time
	(time units)	(time units)
	optimal solution	SA metaheuristic
1	51	89
2	140	139
3	76	74
4	149	148
5	82	53

In order to illustrate, Figs. 9 and 10 show the optimal solution and metaheuristic solution by SA, respectively, for an example with 8 trucks and 5 docks. The same forbidden time windows as in the first example were used. Table 6 shows the completion moment of the last dock assigned to the trucks for this example. The optimal solution is 1,029, while the metaheuristic solution by SA is 1,063. It is important to highlight that dock 1 was the first to be visited, unloading operations were performed before loading operations by all trucks, and travel time among docks was respected, as well as forbidden time windows.

[See PDF for image]

Fig. 9

Optimal solution represented by Gantt chart–8 trucks and 5 docks

[See PDF for image]

Fig. 10

Metaheuristic solution represented by Gantt chart - 8 trucks and 5 docks

Table 6. Ending time of last designated dock–8 trucks and 5 docks

Truck	Ending time	Ending time
	(time units)	(time units)
	optimal solution	SA metaheuristic
1	93	86
2	204	193
3	111	162
4	171	133
5	94	83
6	116	84
7	166	209
8	74	113

The tests continued to be performed for larger sets of trucks and docks with the purpose of validating the proposed model. The largest database for which the LINGO software found the optimal solution had 9 trucks and 5 docks. For databases larger than 9 trucks and 5 docks, the software was unable to find the optimal solution in less than 24 h.

There are other optimization software available, that present a better computational performance, returning the optimal solution with lower performance times. An example of this software is Gurobi, which was also chosen to be used as a tool to obtain the optimal solutions for the exact model proposed in this work.

Considering that the mathematical model was already programmed in LINGO, it was decided not to use any specific programming language in Gurobi, but to generate files in LP format from LINGO’s programming, one of the file formats that Gurobi is capable of reading. A LP file is a text file that structures a linear program and / or mixed integer program in algebraic form. The same problem instances generated and resolved by LINGO were used by Gurobi in order to enable a better comparison.

Although, the exact resolution is not available for all problems. The truck schedule problem is classified as NP-hard, which means that an increase in the problem dimension generates an exponential increase in the resolution time required by the exact model [7]. By increasing the number of trucks and docks in the problem, the time required for resolution increases so much that the exact resolution becomes practically inefficient. Thus, heuristics and metaheuristics implementation appear as a tool to obtain good solutions with significantly shorter performance times.

Based on this, the Simulated Annealing metaheuristic was implemented in Excel, in the Visual Basic for Applications language and it was executed for the same databases used in the exact resolution by software LINGO and Gurobi. In addition to comparing the performance times, the metaheuristic results were also compared to the optimal solution, using GAP equation 19.

19

$$\begin{array}{c}\hfill GAP={\displaystyle \frac{SASolutionOptimalSolution}{SASolution}}\times 100\end{array}$$Table 7 presents a comparison of the results and performance times obtained by the proposed metaheuristic and by the optimization software for problems of different dimensions. It is relevant to mention that the number of docks includes the reception.

Table 7. Comparison between the optimal solution and the solution obtained by the SA metaheuristic

No	No	Optimal	Runtime	Runtime	Solution	GAP	Runtime
of	of	solution	(sec)	(sec)	SA	(%)	(sec)
trucks	docks	(time units)	LINGO	Gurobi	(time units)		SA
5	4	498	3.55	0.44	503	1.0	10.99
6	4	627	33.07	1.31	634	1.1	10.42
7	4	800	68.69	1.95	809	1.1	11.16
7	5	893	238.32	3.22	909	1.8	11.77
8	5	1,029	2,674.82	29.95	1,063	3.2	12.2
9	5	1,223	62,859.92	950.00	1,269	3.6	13.12
10	5	1,382	–	5,509.64	1,432	3.5	14.13

As observed in Table 7, Gurobi showed better computational performance than LINGO by returning optimal solutions with lower performance times. For the problem with 7 trucks and 4 docks, LINGO returned the optimal solution in just under 69 s, while Gurobi returned the solution to the same problem in less than 2 s.

The last row of Table 7 has no value in “Time (sec) LINGO" column, as the software was not able to return the optimal solution to the problem with 10 trucks and 5 docks within 24 h. Although Gurobi presents better computational performance, this software also presented limitations. The biggest instance solved by the software has 10 trucks and 5 docks. The resolution of the instance with 11 trucks and 5 docks took more than 48 h.

As expected, the SA metaheuristic showed shorter performance times when compared to the larger problems’ exact resolutions. Considering the problem instance with 9 trucks and 5 docks as an example, the exact resolution required 62,859.92 s in LINGO and 950 s in Gurobi, while metaheuristic SA returned the best result within 13.12 s. The 1,269 value solution returned by SA is not optimal, but it approaches the optimal value of 1,223, with a 3.6% GAP.

In real scenarios, companies have several docks at their facilities and receive dozens, or even hundreds, of trucks and suppliers by day. In order to approximate the tests to the real dimensions and finalize the evaluation of the proposed metaheuristic, the algorithm was executed for larger problems. Table 8 presents results obtained for different instances using Gurobi software.

Table 8. Simulated annealing results for larger dimension problems using Gurobi software

No	No	Objective function	Runtime
of trucks	of docks	(time units)	(sec)
20	7	8262	102.35
50	9	40,726	1022.16
70	11	75,438	2461.88
75	14	91,282	3811.57
80	14	98,481	4439.96

it is not possible to calculate the GAP for these examples since the optimization software is not able to return the optimal solutions in viable times. However, it is worth emphasizing how fast the metaheuristic is able to solve major problems. The problem with 75 trucks and 14 docks (one being the reception), demanded a computational time of approximately 3,812 s, equivalent to 1 h approximately.

Conclusions

The activities of sequencing and scheduling are of great importance for companies and are not restricted to production only, they can also be applied to other sectors, such as logistics. It is common for companies to perform these activities manually and empirically, which demands time from the employee responsible for the activity, in addition to generating bottlenecks in the production process, long waiting times for equipment and professionals, and increased costs for the company.

The existence of a structured method for these stages of Production Planning and Control can bring significant improvements for companies, such as a more fluid flow of activities, without the presence of bottlenecks and waste; activities automation; reduction in the execution times of activities, waiting times and even company costs.

This paper sought to propose a mathematical model for the truck sequencing and scheduling problem with forbidden time windows, in order to minimize the time spent by drivers within the company and to solve it optimally and approximately. The mathematical model was developed in order to allow adaptation for companies in different sectors.

The mathematical model presented was based on the open shop sequencing problem. By analyzing the studies considered in the literature review, it was found that this was the problem that best adapted to the constraints of the case proposed in this work. The proposed algorithm for the approximate problem resolution was based on the Simulated Annealing metaheuristic.

The proposed mathematical model respected the conditions imposed to the problem, such as forbidden time windows and precedence of unloading activities before loading activities. However, the model presented computational limitations to return optimal solutions when executed by the optimization software LINGO and Gurobi. These limitations were already expected due to the NP-hard classification of truck scheduling problems and they were the motivation for implementing the algorithm based on the Simulated Annealing metaheuristic. Through the computational experiments, the proposed algorithm proved to be robust in meeting the base problem constraints and returning solutions close to the optimal ones, with GAP values below 4% and within acceptable computational times.

Regarding these considerations, the mathematical model presented for the truck sequencing and scheduling problem proved to be viable for small problems. The proposed algorithm based on the Simulated Annealing metaheuristic can be used for larger problems that cannot be solved exactly due to computational limitations, and can even be considered as a tool to be used by companies to solve real vehicle sequencing and scheduling problems.

Future research can explore the limitations of this work in order to include them in the mathematical model scope and make the problem more complete and more faithful to the real situations faced by companies. Examples of limitations to be analyzed are dock capacity constraints and the option of operating docks in parallel. In addition, it is proposed to apply other heuristics or meta-heuristics, such as Genetic Algorithm and Differential Evolution.

Author Contributions

All authors contributed to the study conception and design.

Funding

No funding was received for conducting this study.

Data Availibility Statement

The datasets used in this study were randomly generated.

Declarations

Conflict of interest

The authors declare that they have no conflict of interest.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

References

1. Abreu, LR; Tavares-Neto, RF; Nagano, MS. A new efficient biased random key genetic algorithm for open shop scheduling with routing by capacitated single vehicle and makespan minimization. Eng. Appl. Artif. Intell.; 2021; 104, [DOI: https://dx.doi.org/10.1016/j.engappai.2021.104373] 104373.

2. Ahmadian, MM; Khatami, M; Salehipour, A; Cheng, TCE. Four decades of research on the open-shop scheduling problem to minimize the makespan. Eur. J. Oper. Res.; 2021; 295, 2 pp. 399-426.4280211 [DOI: https://dx.doi.org/10.1016/j.ejor.2021.03.026]

3. Anand, E; Panneerselvam, R. Literature review of open shop scheduling problems. Intell. Inf. Manag.; 2015; 7, 1 pp. 33-52. [DOI: https://dx.doi.org/10.4236/iim.2015.71004]

4. Arenales, M; Armentano, V; Morabito, R; Yanasse, HH. Operational Research for Engineering Courses; 2015; 2 Rio de Janeiro, Elsevier:

5. Bendul, JC; Blunck, H. The design space of production planning and control for industry 40. Comput. Ind.; 2019; 105, pp. 260-272. [DOI: https://dx.doi.org/10.1016/j.compind.2018.10.010]

6. Berghman, L; Leus, R; Spieksma, FCR. Optimal solutions for a dock assignment problem with trailer transportation. Ann. Oper. Res.; 2014; 213, pp. 3-25.3152870 [DOI: https://dx.doi.org/10.1007/s10479-011-0971-7]

7. Bodnar, P; Koster, R; Azadeh, K. Scheduling trucks in a cross-dock with mixed service mode dock doors. Transp. Sci.; 2015; 51, 1 pp. 112-131. [DOI: https://dx.doi.org/10.1287/trsc.2015.0612]

8. Boysen, N; Emde, S; Hoeck, M; Kauderer, M. Part logistics in the automotive industry: Decision problems, literature review and research agenda. Eur. J. Oper. Res.; 2015; 242, 1 pp. 107-120.3286645 [DOI: https://dx.doi.org/10.1016/j.ejor.2014.09.065]

9. Cankaya, B; Wari, E; Tokgoz, BE. Practical approaches to chemical tanker scheduling in ports: a case study on the port of houston. Marit. Econ. Logist.; 2019; 21, pp. 559-575. [DOI: https://dx.doi.org/10.1057/s41278-019-00122-w]

10. Cañas, H; Mula, J; Campuzano-Bolarín, F; Poler, R. A conceptual framework for smart production planning and control in industry 4.0. Comput. Ind. Eng.; 2022; 173, [DOI: https://dx.doi.org/10.1016/j.cie.2022.108659] 108659.

11. Cota, PM; Gimenez, BMR; Araújo, DPM; Nogueira, TH; Souza, MC; Ravetti, MG. Time-indexed formulation and polynomial time heuristic for a multi-dock truck scheduling problem in a cross-docking centre. Comput. Ind. Eng.; 2016; 95, pp. 135-143. [DOI: https://dx.doi.org/10.1016/j.cie.2016.03.001]

12. Escobar-Hervert, L; Pérez-López, JF. Production planning and scheduling optimization model: a case of study for a glass container company. Ann. Oper. Res.; 2020; 286, pp. 529-543.4061491 [DOI: https://dx.doi.org/10.1007/s10479-018-3099-1]

13. Fernandez-Viagas, V; Framinan, JM. Neh-based heuristics for the permutation flowshop scheduling problem to minimise total tardiness. Comput. Oper. Res.; 2015; 60, pp. 27-36.3328036 [DOI: https://dx.doi.org/10.1016/j.cor.2015.02.002]

14. Franzin, A; Stützle, T. Revisiting simulated annealing: A component-based analysis. Comput. Oper. Res.; 2019; 104, pp. 191-206.3894233 [DOI: https://dx.doi.org/10.1016/j.cor.2018.12.015]

15. Fuchigami, H. Y.: A proposal simulated annealing algorithm for proportional parallel flow shops with separated setup times. Produção Online, 14(3), 997–1023 (2014). https://doi.org/10.14488/1676-1901.v14i3.1631

16. Gallo, C; Capozzi, V. A simulated annealing algorithm for scheduling problems. J. Appl. Math. Phys.; 2019; 7, 11 pp. 2579-2594. [DOI: https://dx.doi.org/10.4236/jamp.2019.711176]

17. Gholami, M; Rabbani, M; Samavati, M. Scheduling trucks in fruit cross docks as an open shop problem with edge colouring. Int. J. Autom. Logist.; 2015; 1, 2 pp. 140-149. [DOI: https://dx.doi.org/10.1504/ijal.2015.068894]

18. Guersola, MS; Steiner, MTA; Scarpin, CT. Customers scheduling and clustering as vendor managed inventory enablers. Int. J. Logist. Syst. Manag.; 2019; 34, pp. 56-74. [DOI: https://dx.doi.org/10.1504/IJLSM.2019.102063]

19. Ilin, V; Simic, D; Simic, SD; Simic, S; Saulic, N; Calvo-Rolle, JL. A hybrid genetic algorithm, list-based simulated annealing algorithm, and different heuristic algorithms for the travelling salesman problem. Log. J. IGPL; 2023; 31, 4 pp. 602-617. [DOI: https://dx.doi.org/10.1093/jigpal/jzac028]

20. Jananeeswari, N; Jayakumar, S; Nagamani, M. Single objective for no-wait patial flexible open shop scheduling problem using heuristic algorithms. Int. J. Pure Appl. Math. Sci.; 2017; 10, 1 pp. 95-112.

21. Kiran, D.R.: Production planning and control: a comprehensive approach. Butterworth-Heinemann, (2019)

22. Kirkpatrick, S; Gelatt, CD; Vecchi, P. Optimization by simulated annealing. Science; 1983; 220, pp. 671-680.702485 [DOI: https://dx.doi.org/10.1126/science.220.4598.671]

23. Kubiak, W. A Book of Open Shop Scheduling: Algorithms; 2022; Complexity and Applications, Springer: [DOI: https://dx.doi.org/10.1007/978-3-030-91025-9]

24. Ladier, A; Alpan, G. Robust cross-dock scheduling with time windows. Comput. Ind. Eng.; 2016; 99, pp. 16-28. [DOI: https://dx.doi.org/10.1016/j.cie.2016.07.003]

25. Ladier, A; Alpan, G. Cross-docking operations: Current research versus industry practice. Omega; 2016; 62, pp. 145-162. [DOI: https://dx.doi.org/10.1016/j.omega.2015.09.006]

26. Lee, TS; Loong, YT. A review of scheduling problem and resolution methods in flexible flow shop. Int. J. Ind. Eng. Comput.; 2019; 10, 1 pp. 67-88. [DOI: https://dx.doi.org/10.5267/j.ijiec.2018.4.001]

27. Liao, TW; Egbelu, PJ; Chang, PC. Simultaneous dock assignment and sequencing of inbound trucks under a fixed outbound truck schedule in multi-door cross docking operations. Int. J. Prod. Econ.; 2013; 141, 1 pp. 212-229. [DOI: https://dx.doi.org/10.1016/j.ijpe.2012.03.037]

28. Liu, W; Jin, Y; Price, M. A new improved neh heuristic for permutation flowshop scheduling problems. Int. J. Prod. Econ.; 2017; 193, pp. 21-30. [DOI: https://dx.doi.org/10.1016/j.ijpe.2017.06.026]

29. Mattos, M; Kleina, M; Marques, MAM; Silva, WA. Aplicação de algoritmos evolucionários na otimização de um recorte de uma cadeia de suprimentos de papel. Exacta; 2021; 19, 3 pp. 706-728. [DOI: https://dx.doi.org/10.5585/exactaep.2021.16318]

30. Metropolis, N; Rosenbluth, AW; Rosenbluth, MN; Teller, AH; Teller, E. Equation of state calculations by fast computing machines. J. Chem. Phys.; 1953; 21, pp. 1087-1092. [DOI: https://dx.doi.org/10.1063/1.1699114]

31. Naderi, B; Zandieh, M. Modeling and scheduling no-wait open shop problems. Int. J. Prod. Econ.; 2014; 158, pp. 256-266. [DOI: https://dx.doi.org/10.1016/j.ijpe.2014.06.011]

32. Nawaz, M; Enscore, EE, Jr; Ham, I. A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega; 1983; 11, 1 pp. 91-95. [DOI: https://dx.doi.org/10.1016/0305-0483(83)90088-9]

33. Ogbu, FA; Smith, DK. The application of the simulated annealing algorithm to the solution of the $n/m/$$C_{\mathit{max}}$ flowshop problem. Comput. Oper. Res.; 1990; 17, 3 pp. 243-253.1043095 [DOI: https://dx.doi.org/10.1016/0305-0548(90)90001-N]

34. Parihar, A.S., Khare, S.: Prodution planning and control: an overview of production systems and production planning and control (2021). ISBN 979-8504810546

35. Penchev, P; Vitliemov, P; Georgiev, I. Optimization model for production scheduling taking into account preventive maintenance in an uncertainty-based production system. Heliyon; 2023; 9, 7 [DOI: https://dx.doi.org/10.1016/j.heliyon.2023.e17485] e17485.

36. Pinedo, ML. Scheduling: Theory, Algorithms, and Systems; 2016; New York, Springer: [DOI: https://dx.doi.org/10.1007/978-3-319-26580-3]

37. Prata, BA; Nagano, MS; Fróes, NJM; Abreu, LR. The seeds of the neh algorithm: an overview using bibliometric analysis. Oper. Res. Forum; 2023; [DOI: https://dx.doi.org/10.1007/s43069-023-00276-7]

38. Puka, R., Duda, J., Stawowy, A.: Input sequence of jobs on neh algorithm for permutation flowshop scheduling problem. Manag. Prod. Eng. Rev. 13(1), 32–43 (2022). https://doi.org/10.24425/mper.2022.140874

39. Ramesh, C; Kamalakannan, R; Karthik, R; Pavin, C; Dhivaharan, S. A lot streaming based flow shop scheduling problem using simulated annealing algorithm. Mater. Today: Proc.; 2021; 37, pp. 241-244. [DOI: https://dx.doi.org/10.1016/j.matpr.2020.05.108]

40. Sakuramoto, C; Di Serio, LC; Bittar, AV. Impact of supply chain on the competitiveness of the automotive industry. RAUSP Manag. J.; 2019; 54, 2 pp. 205-225. [DOI: https://dx.doi.org/10.1108/RAUSP-07-2018-0051]

41. Satyro, WC; Spinola, MM; Almeida, CMVB; Giannetti, BF; Sacomano, JB; Contador, JC; Contador, JL. Sustainable industries: Production planning and control as an ally to implement strategy. J. Clean. Prod.; 2021; 105, [DOI: https://dx.doi.org/10.1016/j.jclepro.2020.124781] 124781.

42. Shahmardan, A; Sajadieh, MS. Truck scheduling in a multi-door cross-docking center with partial unloading - reinforcement learning-based simulated annealing approaches. Comput. Ind. Eng.; 2020; 139, [DOI: https://dx.doi.org/10.1016/j.cie.2019.106134] 106134.

43. Sharma, H.: Production planning and control. BookRix (2019)

44. Sharma, M; Sharma, M; Sharma, S. An improved neh heuristic to minimize makespan for flow shop scheduling problems. Decis. Sci. Lett.; 2021; 10, pp. 311-322. [DOI: https://dx.doi.org/10.5267/j.dsl.2021.2.006]

45. Silva, NCO; Scarpin, CT; Pécora, JEP, Jr; Ruiz, A. Online single machine scheduling with setup times depending on the jobs sequence. Comput. Ind. Eng.; 2019; 129, pp. 251-258. [DOI: https://dx.doi.org/10.1016/j.cie.2019.01.038]

46. Slack, N., Brandon-Jones, A., Burgess, N.: Operations Management. Pearson, 10th edition (2022)

47. Tadumadze, G., Emde, S.: Loading and scheduling outbound trucks at a dispatch warehouse. IISE Trans. 54(8), 770–784 (2022). https://www.tandfonline.com/doi/10.1080/24725854.2021.1983923

48. Theophilus, O; Dulebenets, MA; Pasha, J; Abioye, OF; Kavoosi, M. Truck scheduling at cross-docking terminals: a follow-up state-of-the-art review. Sustainability; 2019; 11, 19 5245. [DOI: https://dx.doi.org/10.3390/su11195245]

49. Tosun, Ö; Marichelvam, MK; Tosun, N. A literature review on hybrid flow shop scheduling. Int. J. Adv. Oper. Manag.; 2020; 12, 2 pp. 156-194. [DOI: https://dx.doi.org/10.1504/IJAOM.2020.108263]

50. Wirth, M; Emde, S. Scheduling trucks on factory premises. Comput. Ind. Eng.; 2018; 126, pp. 175-186. [DOI: https://dx.doi.org/10.1016/j.cie.2018.09.023]

51. Wu, GH; Chen, YT; Chen, KH. Hybrid algorithms for inbound and outbound truck scheduling in cross-docking systems. Appl. Sci.; 2022; 12, 21 10931. [DOI: https://dx.doi.org/10.3390/app122110931]

52. Xiong, H; Shi, S; Ren, D; Hu, J. A survey of job shop scheduling problem: The types and models. Comput. Oper. Res.; 2022; 142, 4379237 [DOI: https://dx.doi.org/10.1016/j.cor.2022.105731] 105731.

53. Zhang, J; Ding, G; Zou, Y; Qin, S; Fu, J. Review of job shop scheduling research and its new perspectives under industry 4.0. J. Intell. Manuf.; 2019; 30, pp. 1809-1830. [DOI: https://dx.doi.org/10.1007/s10845-017-1350-2]

54. Zobolas, GI; Tarantilis, CD; Ioannou, G. Solving the open shop scheduling problem via a hybrid genetic-variable neighborhood search algorithm. Cybern. Syst.; 2019; 40, 4 pp. 259-285. [DOI: https://dx.doi.org/10.1080/01969720902830322]