Advertisement

Advertisement

Modified genetic algorithm to solve worker assignment problem with time windows

  • Open access
  • Published: 21 February 2024
  • Volume 2 , article number  1 , ( 2024 )

Cite this article

You have full access to this open access article

  • Alfian Akbar Gozali 1  

207 Accesses

Explore all metrics

In recent years, the demand for electronic products has been increasing rapidly. T mounting technology (SMT) line is one of the production areas for electronic products, directly affecting this situation. In an SMT line, multiple machines mount electronic parts to the board. The worker must complete work when the parts used in these machines are within the remaining parts available for replacement. When a worker fails to replace parts at the right time, the production line stops, and delays occur. Besides, there may be a designated worker who should be assigned to each task. In the current situation, workers’ work procedures are not optimized, so they should schedule work procedures for each worker. This problem is called Worker Assignment Problem with Time Window (WAPTW). This paper proposes a method to solve WAPTW called Genetic Algorithm with Local Restriction (GALR). GALR combines a genetic algorithm (GA) and local search with local restriction. This paper’s main contribution is introducing WAPTW as a novel real-world optimization problem in an electricity company, its mathematical formulation, and a proposed GALR to solve WAPTW. The experiment shows that the proposed method could yield the best result in real-world WAPTW compared with other methods.

Similar content being viewed by others

genetic algorithm assignment problem

Genetic algorithm with normal boundary intersection for multi-objective early/tardy scheduling problem with carbon-emission consideration: a Pareto-optimum solution

Hudaifah Hudaifah, Andriansyah Andriansyah, … Haitham Saleh

genetic algorithm assignment problem

Minimizing the makespan and carbon emissions in the green flexible job shop scheduling problem with learning effects

Zhi Li & Yingjian Chen

genetic algorithm assignment problem

Distributed-elite local search based on a genetic algorithm for bi-objective job-shop scheduling under time-of-use tariffs

Bobby Kurniawan, Wen Song, … Shigeru Fujimura

Avoid common mistakes on your manuscript.

1 Introduction

The demand for electronic products has increased rapidly in recent years, as discussed by [ 14 ]. [ 16 ] research pointed this has led to many manufacturers and electronic companies competing to implement process improvement to meet this demand. One area affected is the surface mounting technology (SMT) line, as mentioned by [ 19 ]. In research by [ 11 ], an SMT line with multiple machines mounted electronic parts to the board. The worker must complete work when the parts used in these machines are within the remaining parts available for replacement. When a worker fails to replace parts at the right time, the production line stops, and delays occur. Besides, there may be a designated worker who should be assigned to each task.

The electricity company has a clear objective of optimizing the efficiency of the SMT line process, which can be achieved by minimizing delays in production activities. However, the current situation is not optimized, and production efficiency is decreasing due to frequent line stoppages. To address this issue, the electricity company should implement a Worker Assignment Problem with Time Window (WAPTW) to schedule work procedures for each worker. This problem is similar to other cases such as [ 15 , 18 ], which carried out the Vehicle Routing Problem with Time Window (VRPTW), [ 13 ] with Manpower Allocation Problem with Time Window (MAPTW), and [ 2 , 5 ] with Manpower Allocation Problem with Time Window and Job-Teaming Constraints (MAPTWTC). This optimization strategy is necessary and beneficial for the electricity company.

The differences between WAPTW and other cases are (1) the number of workers available is predetermined in advance, and (2) each task is provided with a time window to indicate the end of the task. In WAPTW, the objective is to assign multiple tasks to workers fairly. WAPTW will use a weighted sum of some penalties as the objective function and then optimize it. The penalties include a tardiness penalty for failure to assign work to a worker, a total travel distance penalty for each worker, and a balance penalty for total work time between workers. WAPTW is classified as an NP-hard problem.

In this study, the authors proposed a method to solve WAPTW and analyze its performance. This research’s main contribution is introducing WAPTW as a novel real-world optimization problem in an electricity company, its mathematical formulation, and a proposed method to solve WAPTW. Combining the genetic algorithm (GA) and local search, called local restriction, is used to solve this problem. This proposed method is called a Genetic Algorithm with Local Restriction (GALR).

To speed up the search time, GALR lines up tasks close to each other regarding their time window and establishes local constraints to ensure that genetic manipulations were actively performed in the time window’s vicinity.

This paper comprises six sections, furthering our understanding of the WAPTW problem and its mathematical formulation. In Sect.  2 , we explore the WAPTW problem and its mathematical formulation, while Sect.  3 introduces the main idea of GALR in detail. Section  4 focuses on implementing GALR for the WAPTW problem. Section  5 discusses the experiment and analyzes its result. Finally, Sect.  6 summarizes the works presented and concludes the problem stated in the first section.

2 Worker assignment problem with time window

As discussed in Sect.  1 , WAPTW is an optimization problem that models the situation of workers on the SMT line. The number of available workers is predetermined, and each task is provided with a time window to indicate the end of the task. Workers begin at a location where their first task is located and then move to the location of the next task they are responsible for, repeating this process until all tasks are completed. Furthermore, workers who arrive early must wait, which is a beneficial feature of this optimization problem.

The WAPTW problem has distinct specifications when compared to other worker scheduling problems, such as VRPTW by [ 15 , 18 ], MAPTW by [ 13 ], and MAPTWTC by [ 2 , 5 ]. Table 1 compares WAPTW and other problems, with the noteworthy difference being that soft values in time windows permit the scheduling of tasks outside of the window, whereas hard values do not. WAPTW has different specifications that make it a valuable problem to consider.

It is commendable that the factories have taken the initiative to equip each machine used in product production with an alarm system. This system encourages the workers to work efficiently by sounding an alarm at the target location before the production line stops due to a partial break from the target machine.

It is essential to ensure that workers who are not working do not cause any delays in the production line, as these can be costly. Unexpected stoppages in the production line can impact product delivery times and worker costs, so every effort must be made to minimize them. Doing so benefits the company and its employees, allowing for a more efficient and cost-effective production process.

Figure  1 clearly illustrates that the alarm will sound between the latest end time (LFT) duration and the earliest end time (EFT) duration. This approach determines how changing the alarm-sounding timing affects the work results of a worker. To further this, we have established an \(\alpha\) to calculate the trigger formulation, as demonstrated in Eq.  1 . The objective is to promptly ensure the worker can be informed of the alarm.

figure 1

Alarm sound illustration in the real factory

2.1 Problem formulation

The problem definition of WAPTW has been formulated into a mathematical expression presented in the subsequent subsection.

2.1.1 Parameters

W : Set of workers

w : \(w\in W\)

T : Set of tasks

i : \(task_i\) ; j : \(task_j\)

\(i,j \in T\)

\(e_i\) : Earliest End Time of \(task_i\)

\(l_i\) : Latest End Time of \(task_i\)

\(d_{ij}\) : Distance between \(task_{i}\) and \(task_{j}\)

\(t_i\) : Processing Time of \(task_i\)

\(w_{iw}\) : \({\left\{ \begin{array}{ll} 1, &{}\text {if worker} w \text {can perform }task_i\\ 0, &{}otherwise \end{array}\right. }\)

\(weight_i\) : Weight of \(penalty_i\)

2.1.2 Decision variables

\(x_{ijw}\) : Worker w passed \(task_i\) and \(task_j\)

\(i\ne j,j\ne n+1,j\ne 0\)

\(x_{ijw}: {\left\{ \begin{array}{ll} 1, &{}w \text { passes }task_i \wedge task_j\\ 0, &{}otherwise \end{array}\right. }\)

n : total number of tasks

\(E_{iw}\) : Time at worker w finished \(task_i\)

\(x_{iw}\) : Worker w performs \(task_i\)

\(x_{iw}: {\left\{ \begin{array}{ll} 1, &{}w \text { performs }task_i\\ 0, &{}otherwise \end{array}\right. }\)

2.1.3 Objective function

The main objective of the Weighted Average Penalty Total Weight (WAPTW) is to reduce the accumulation of all weighted penalties, as demonstrated in Eq.  2 . WAPTW can ensure that the system remains stable and efficient by minimizing the accumulation of penalties.

The paper presents a formulation of the objective function, as expressed in Eqs.  3 , 4 , and 5 . This formulation considers the three penalties of tardiness, total distance, and working time balance, each with its weight ( \(weight_i\) ) assigned to the penalty \(p_i\) .

\(p_1:\) Tardiness penalty

\(p_2:\) Total distance penalty

\(p_3:\) Working time balance penalty

3 Genetic algorithm with local restriction

It is generally accepted that the scheduling problem is NP-complete, as mentioned by [ 1 ], implying that no known algorithms exist to identify optimal solutions. Exhaustive search methods can be used to solve scheduling problems. However, their execution time increases exponentially as the problem size increases, making them practically infeasible. This paper proposes a heuristic approach, which utilizes a genetic algorithm and local search with local restriction (GALR) to tackle this scheduling problem. This promising development could be a viable alternative to exhaustive search methods.

3.1 Genetic Algorithm

The Genetic Algorithm, introduced by [ 7 ], is an exemplary type of Evolutionary Algorithm. This algorithm seeks to emulate natural evolution by creating a population of potential solutions and exploring the search space to find near-optimal solutions to optimization problems. The Genetic Algorithm is a remarkable tool, and its efficacy in solving complex optimization problems is commendable.

The Genetic Algorithm (GA) is an effective optimization technique that has been successfully applied to a variety of optimization problems, including the Vehicle Routing Problem with Time Windows (VRPTW) by [ 6 , 10 ], and general optimization benchmark problems by [ 3 ]. GA does not exhaustively search the entire solution space but instead starts with a small population of possible solutions and iteratively evolves them toward better solutions. Ultimately, a nearly optimal result for the optimization problem is yielded. Thus, GA has the potential for solving WAPTW-related problems and should be considered for any optimization problem.

3.2 Local restriction

[ 8 , 12 ] used local search to complement local search implementation, an established method for solving optimization problems. Examples of local search implementation include memetic algorithms, which combine GA and local search, and the Dual Migration Localized Island Model GA (DM-LIMGA) conducted by [ 4 ], which utilizes three types of mutations as its local search. By actively swapping tasks in the vicinity, local search has been proven to be an effective method of finding the right solution and reducing execution time. Furthermore, [ 9 , 17 ] has demonstrated that local search can produce excellent results when solving VRPTW and WAPTW.

The local restriction is a local search that restricts the extent of genetic manipulation exchange of genes, such as GA mutation. In WAPTW, since every task has a time window, which means work end times, the optimal gene sequences are assumed to be close to each time window. Regular genetic manipulation is characterized by a global search, which is expected to make the solution much worse with no limit on the scope of task exchange, and the search time to find a suitable solution will be enormous.

For the efficiency of swapping tasks in the vicinity, we limit the range of genetic manipulation that can be performed. We believe that adopting local restrictions solves the problem and allows us to seek the right solution in less execution time by efficiently exchanging tasks.

For these reasons, we propose a method that combines the Genetic Algorithm with Local Search and Local Restriction (GALR) to solve WAPTW. The GALR proposed in this paper has been modified to design encoding, mutation, and local search to suit the problem.

4 GALR for WAPTW

The main objective of GALR is to solve the Worker Assignment Problem in the Time Window (WAPTW) by optimizing the procedures of workers in the Surface Mount Technology (SMT) line. This objective can be achieved in three main steps: formulating the problem for WAPTW, developing a simulator for predicting the task time for a worker in the SMT line, and solving WAPTW with an optimal algorithm. The flow of solving WAPTW using GALR is illustrated in Fig.  2 , an effective and efficient approach to optimize the worker’s procedures in the SMT line.

figure 2

WAPTW using GALR Flowchart

4.1 Encoding

GALR provides two integer types of chromosomes for one individual. The first type is Gene Type, with an index containing task identifiers. The size of the index is the total number of tasks that need to be scheduled. Moreover, to determine the sequence of task allocation, the proposed method gives higher priority to task identifiers with a high gene type index and lower priority to those with a low index.

The second type is Sub-gene Type, which has the index containing the worker identifier. The size of the index is the same as Gene Type. The index of Sub-gene Type is tied to the task identifier of Gene Type.

By treating the chromosome like this, each worker can determine which task is necessary according to their responsibility. As mentioned in Sect.  2 , each task should contain the location where work must be done, processing time, latest end time, earliest end time, and workable worker information. Therefore, when the GALR inserts its worker identifier into Sub-gene Type, a worker will be selected according to workable worker information, which is also his responsibility. Figure  3 depicts gene and sub-gene type encoding of GALR used in this paper.

figure 3

GALR gene and Sub-gene type encoding

For the initialization, GALR will generate individuals as many as population size (N). An individual will be inserted into the index, starting with the earliest task at the latest end time. The remaining individuals are randomly selected according to the task. Then they will be inserted into the index according to their selection sequence.

According to the time neighborhood relationship, the initial population splits into each task’s successor and predecessor groups. The first step is putting all tasks in order, starting with the latest task at the end time. Next, set a movable range (240 s) as the neighborhood time range.

Then pick two random tasks, and check the difference between the latest end time and the other task. If it is equal to or less than the movable range, set the previous task into the predecessor group’s other task. Finally, set the back task to the successor group of the previous task. This relationship is used to change the allocation priority of tasks.

4.2 Selection

GALR uses tournament selection as a method of selection according to their fitness function. This paper utilized a maximization objective function; thus, Eq.  2 must be reversed. Equation  6 illustrates the fitness formulation utilized in this paper.

4.3 Crossover

GALR employs a modified form of one-point crossover to generate offspring, as illustrated in Fig.  4 . This process involves selecting two random individuals from the population who serve as crossover parents. The resultant offsprings inherit some of the information from both parents, with the task sequence of Gene Type being the only element that changes, while the worker sequence of Sub-gene Type is passed on to the offspring.

figure 4

Crossover in gene and Sub-gene type chromosome

4.4 Mutation

Individuals in a population with a predetermined ratio (mutation probability) to the total number of individuals (population) are subject to mutation. The mutation will be performed separately for Gene and Sub-gene Type chromosomes. Half of the individuals that will be mutated are subject to mutation for the task. Contrary, the other half is subject to mutation for a worker.

Figure  5 illustrates the task mutation step. There are three steps for task mutation: (1) select the target index (random), (2) get the point that is in the vicinity of the target index (random), and (3) swap the task between 1 and 2.

figure 5

Mutation task steps

Figure  6 illustrates the worker mutation step. There are two steps for worker mutation: (1) select the target index (random) and (2) change worker (Change the task from the current worker to another randomly available worker).

figure 6

Mutation worker steps

4.5 Local restriction

For individuals in a population, do a local restriction for individuals with a high fitness value (individuals with a small total penalty) with a specific ratio (local restriction ratio). Local restriction processes the work schedule corresponding to an individual, starting with the highest allocation priority task. If the task’s end time is before the earliest end time, the task’s priority is raised by one. This operation will reduce the time penalty. Figure  7 depicts the local restriction steps.

figure 7

Local restriction step

Compare the latest end time of two tasks, starting with the order of priority in which the worker is responsible for the task. If the latest end time of a task with a lower allocation priority is greater than that of a task with a higher allocation priority, and the two tasks are not related to a predecessor or a successor group, swap the allocation priority of the two tasks. By doing this process, a more efficient search can be achieved. The adjusted pseudo-code is shown in Fig.  8 .

figure 8

Adjusting chromosome

4.7 Decoding

Decoding is a reverse process yielding a schedule of tasks assigned to each worker in order of allocation priority. In doing so, derive the start and end times of each task. Each worker always keeps the end time of the previous task. Each worker can determine if it is possible to finish in the time window of each task. The time penalty occurs if the worker’s task’s end time is earlier than the earliest end time. After this sequence, individuals with the lowest penalty in a final set of individuals in a generation are derived as the approximate optimal solution. The decoding pseudo-code is shown in Fig.  9 .

figure 9

GALR decoding

5 Experimental result

The primary purpose of this paper is to validate the proposed algorithm and assess its performance. The experiment was conducted with data from an actual SMT line to demonstrate the proposed algorithm’s efficacy in a real-world setting. The results of the GALR scheduling were compared to the existing workers scheduling in the factory to evaluate the algorithm’s effectiveness.

5.1 Parameters of the experiment

This experiment utilized six parameter values for comparison: total time penalty, total distance penalty, total balance penalty, line stop, line counter, and module counter. Each of these parameters has distinct functions in the experiment. Total time penalty measures the total duration of the experiment; total distance penalty measures the total distance traveled; total balance penalty measures the balance of the robot; line stop measures the number of times the robot stops on the line; line counter measures the number of lines crossed; and module counter measures the number of modules crossed.

Total time penalty . It is the aggregate of all time penalties workers incur for failing to complete tasks within their assigned time windows. This penalty is a real consequence for factory workers who cannot meet deadlines and should be taken seriously to ensure that tasks are completed on time.

How to calculate the time window of the task:

\(l_i\) : (remaining parts- lower limit)/used amount of parts per product * cycle time of product

\(l_i\) : (remaining parts - upper limit)/used amount of parts per product * cycle time of product

lower limit = minimum number of product * used amount per product + feeder length + Number of parts consumed during the operation

upper limit = maximum number of product* used amount per product + feeder length + Number of parts consumed during the operation

Total distance penalty . The total distance penalty incurred by each worker must be calculated and taken into account to accurately assess the workforce’s overall performance. This sum must be determined to ensure that all employees are held to the same standards and that discrepancies are properly addressed. Failure to do so could lead to an inaccurate representation of the team’s collective effort.

Total balance penalty . The aggregate difference between each worker’s actual working time and average working time must be calculated to determine the total sum. This sum is essential to ensure that all workers contribute an equitable amount of effort and that any discrepancies are properly addressed.

Line stop . On multiple occasions, the production line has been halted due to the end time of the worker’s task surpassing the latest end time of the task. This has caused production delays, resulting in decreased overall efficiency. Therefore, the end times of tasks must be monitored closely to ensure that the production line remains operational.

Line counter . It is imperative to keep track of the number of times each worker has moved across the production line to perform other tasks. These data are essential to ensure that the workflow is efficient and that the workers can complete their tasks in an organized and timely manner. Keeping track of this information is critical to maintaining a successful production line.

Module counter . It is imperative to note the number of times each worker has shifted to a different task within the same line. This is an important metric to track to ensure the production line’s efficient workflow. Each worker must be mindful of the number of times they have moved to a different task within the same line to maximize productivity.

5.2 Data description

Table 2 describes the data used in this paper.

5.3 GALR parameters’ configuration

Table 3 presents the configuration of GALR parameters employed in this paper. The table provides a clear overview of the parameters and their respective values, which were used to evaluate the performance of the proposed algorithm.

The max generation parameter refers to the maximum number of generations (or iterations) the algorithm will run for. The values (1000, 3000, 5000) likely represent different configurations or scenarios to test how the algorithm performs over various generations. Population size is set to 30, which means that there are 30 individual solutions (or "chromosomes") in each generation. A larger population might not only increase the chances of finding a good solution but also require more computational resources.

The crossover probability indicates how often this operation will occur. When two solutions are selected, there is a 0.2 probability they willl undergo crossover. Mutation probability is set to 0.8, which means 80% of the offspring will undergo some form of mutation after being generated.

The local search ratio is an additional step in refining a solution by exploring its immediate neighborhood. The ratio indicates how frequently this operation will occur. Here, 0.1 (or 10%), the solutions in a generation will undergo local search.

5.4 Experimental result

The experimental results in Table 4 demonstrated that the GALR had a total time penalty of zero for generations 1000, 3000, and 5000, confirming that the workers were assigned to all tasks within these time frames. As the "Alarm" value ( \(\alpha\) ) increases significantly from 0.0 to 1.0, the total time penalty increases significantly. It indicates that as \(\alpha\) increases, the time performance deteriorates. This trend is particularly noticeable when \(\alpha\) goes from 0.8 to 1.0, showing the largest jump in a time penalty. The total distance penalty also increases with the increment of \(\alpha\) , but not as dramatically as the total time penalty. The total balance penalty stays relatively stable across different \(\alpha\) values, slightly decreasing when \(\alpha\) =1.0.

The line stop count shows a rising trend as \(\alpha\) increases. At \(\alpha\) =0.0 and \(\alpha\) =0.2, there are no line stops, but as \(\alpha\) increases, so does the number of line stops. This might indicate that a higher \(\alpha\) leads to a more unstable or less efficient system. The line counter increases marginally as \(\alpha\) increases, suggesting that more lines are processed with an increase in \(\alpha\) . The module counter, on the other hand, decreases as \(\alpha\) increases. This could mean that with a higher \(\alpha\) , fewer modules are processed. Regarding CPS (presumably a measure of time or speed), there is not a clear trend as \(\alpha\) increases. There is a dip at \(\alpha\) =0.6, after which the CPS value increases again. However, applying the Genetic Algorithm with Local Refinement (GALR) yielded a value of 0, confirming its effectiveness in solving the Weighted Assembly Line Problem with Time Windows (WAPTW). In conclusion, GALR is an effective method for solving WAPTW.

For the next experiment, based on the result provided in Table 5 , it could be concluded that among the four methods (GALR, GA+LR, GA+LS, and GA), the GALR method seems to perform the best in terms of penalties. It has zero time and balances penalties for all MAX GENE values, and the total distance penalty also shows a decreasing trend as the MAX GENE value increases. The GA+LR and GA+LS methods have varied results but have less time and balance penalties than GA. However, these methods still perform less efficiently than GALR. The GA method appears to be the least effective among all. The time penalty is the highest for this method for all MAX GENE values, and it has more line stops.

Regarding the module counter, all methods seem to increase with the increment of the MAX GENE value, but the increase is not significant. Considering the CPS (ms), all methods show an increasing trend as the MAX GENE increases, which means all the methods take more time to solve the problem as the MAX GENE value increases. The line counter shows some differences between methods; the GALR method is the best, with less line count, while the GA+LS method has the most. In conclusion, the GALR method is the best regarding penalties and line counters. However, as the complexity of the problem increases (MAX GENE), all methods require more time (CPS ms) to solve the problem.

6 Conclusion

This paper presents an in-depth study of the Worker Assignment Problem with Time Window (WAPTW), a worker scheduling problem in SMT lines. WAPTW exhibits several unique characteristics that distinguish it from other scheduling problems, such as MAPTW, MAPTWTC, and VRPTW. These differences include constraints on assigning workers to tasks, the soft time window of a task, and the main objective of efficiently scheduling work while ensuring uniform work time among workers.

This paper thoroughly discusses the mathematical formulation of the Weighted Asymmetric Parallel Task Window (WAPTW) problem, defining the parameters, decision variables, and objective function. To address this challenge, a novel heuristic algorithm, named Genetic Algorithm with Local Restriction (GALR), is proposed. GALR is a combination of a Genetic Algorithm, Local Search, and Local Restriction, which enables a more efficient solution search, taking into account the time window of each task.

The experiments involved two key aspects: comparing optimization methods and examining the influence of a critical parameter, \(\alpha\) . In the method comparison experiment, the GALR algorithm significantly outperformed the other tested algorithms, namely GA+LR, GA+LS, and GA. GALR achieved the lowest penalties in time, distance, and balance. However, as the complexity of the problem escalated, represented by the MAX GENE parameter, all algorithms needed a longer duration to derive a solution, including GALR.

Subsequently, the impact of the “Alarm” parameter ( \(\alpha\) ) was scrutinized. The results manifested a considerable degradation in performance as \(\alpha\) increased. This decline was most prominent in total time penalty and line stop counts. Nevertheless, we also observed an uptick in the line counter with increasing \(\alpha\) , suggesting that more lines were processed even though penalties and stops rose. From the experiments, an intriguing commonality was the relative stability of the balance penalty, largely unchanged across different methods or varying \(\alpha\) values.

These results underscore the effectiveness of the proposed GALR algorithm for the WAPTW problem and highlight the crucial role of optimal parameter selection, particularly that of \(\alpha\) , in ensuring efficient system performance. Future research should consider exploring alternative algorithms, such as Particle Swarm Optimization (PSO) or the Island-Based GA model for the WAPTW problem, to widen the scope of effective solutions.

Data availability

Not applicable.

Abdullahi M, Ngadi MA, Dishing SI, Abdulhamid SM, Ahmad BI (2019) An efficient symbiotic organisms search algorithm with chaotic optimization strategy for multi-objective task scheduling problems in cloud computing environment. J Netw Comput Appl 133:60–74

Article   Google Scholar  

Garcia, C. & University of Mary Washington, College of Business, 1301 College Avenue, Fredericksburg, VA, 22401, USA (2023) The synchronized multi-assignment orienteering problem. J Ind Manag Optim 19(3):1790–1812

Article   MathSciNet   Google Scholar  

Gozali AA, Fujimura S (2019) DM-LIMGA: dual migration localized island model genetic algorithm—a better diversity preserver island model. Evol Intel 12(4):527–539. https://doi.org/10.1007/s12065-019-00253-2

Gozali AA, Kurniawan B, Weng W, Fujimura S (2019) Solving university course timetabling problem using localized island model genetic algorithm with dual dynamic migration policy. IEEJ Trans Electr Electron Eng 15(3):389–400. https://doi.org/10.1002/tee.23067

Guastaroba G, Côté J-F, Coelho LC (2021) The Multi-Period workforce scheduling and routing problem. Omega 102:102302

Han M, Wang Y-B (2020) A solution to VRPTW based on improved GA-AMMAS algorithm. J Phys: Conf Ser 1486:032015. https://doi.org/10.1088/1742-6596/1486/3/032015

Holland JH (1992) Adaptation in natural and artificial systems adaptation in natural and artificial systems. The MIT Press, Cambridge

Book   Google Scholar  

Khebbache-Hadji S, Prins C, Yalaoui A, Reghioui M (2011) Heuristics and memetic algorithm for the two-dimensional loading capacitated vehicle routing problem with time windows. CEJOR 21(2):307–336. https://doi.org/10.1007/s10100-011-0204-9

Kilby P, Prosser P, Shaw P (1999) Guided local search for the vehicle routing problem with time windows. Meta-heuristics: advances and trends in local search paradigms for optimization, Springer US, pp 473–486

Mazdarani F, Farid Ghannadpour S, Zandieh F (2023) Bi-objective overlapped links vehicle routing problem for risk minimizing valuables transportation. Comput Oper Res 153:106177

Mumtaz J, Guan Z, Yue L, Wang Z, Ullah S, Rauf M (2019) Multi-Level planning and scheduling for parallel PCB assembly lines using hybrid spider monkey optimization approach. IEEE Access 7:18685–18700

Neri F, Cotta C, Moscato P (2012) Handbook of memetic algorithms. Springer, Berlin Heidelberg

Polnik M, Riccardi A, Akartunalı K (2021) A multistage optimisation algorithm for the large vehicle routing problem with time windows and synchronised visits. J Oper Res Soc 72(11):2396–2411

Preeti Wadhwani PS (2020 August) Consumer electronics market size by product (audio & video equipment [personal, professional], major household appliance, small household appliance, digital photo equipment [personal, professional]), by application (personal, professional), industry analysis report, regional outlook, growth potential, competitive market share & forecast, 2020-2026 (techreport). 4 North Main Street, Selbyville, Delaware 19975 USAGlobal Market Insights

Qi R, Li J-Q, Wang J, Jin H, Han Y-Y (2022) QMOEA: A q-learning-based multiobjective evolutionary algorithm for solving time-dependent green vehicle routing problems with time windows. Inf Sci 608:178–201

Statista (2020) Electronics & media ecommerce report 2020 (techreport). 175 Greenwich Street, New York 10007 USAStatista Digital Market Outlook

Wahyuningsih S, Satyananda D (2020) Improvement of solution using local search method by perturbation on VRPTW variants. J Phys Conf Ser 1581:012004. https://doi.org/10.1088/1742-6596/1581/1/012004

Wang Y, Ran L, Guan X, Fan J, Sun Y, Wang H (2022) Collaborative multicenter vehicle routing problem with time windows and mixed deliveries and pickups. Expert Syst Appl 197(116690):116690

Wu K, Bozzi M, Fonseca NJG (2021) Substrate integrated transmission lines: review and applications. IEEE J Microwaves 1(1):345–363

Download references

Acknowledgements

Author information, authors and affiliations.

Faculty of Applied Science, Telkom University, Jl. Telekomunikasi, Bandung, 40257, Jawa Barat, Indonesia

Alfian Akbar Gozali

You can also search for this author in PubMed   Google Scholar

Corresponding author

Correspondence to Alfian Akbar Gozali .

Ethics declarations

Competing interests.

The authors declare that they have no competing interests.

Additional information

Publisher's note.

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

Rights and permissions

Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/ .

Reprints and permissions

About this article

Gozali, A.A. Modified genetic algorithm to solve worker assignment problem with time windows. Industrial Artificial Intelligence 2 , 1 (2024). https://doi.org/10.1007/s44244-024-00015-9

Download citation

Received : 17 June 2023

Accepted : 14 February 2024

Published : 21 February 2024

DOI : https://doi.org/10.1007/s44244-024-00015-9

Share this article

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

  • Worker assignment
  • Genetic algorithm
  • Local search
  • Local restriction
  • Find a journal
  • Publish with us
  • Track your research

Improved Genetic Algorithm for Weapon Target Assignment Problem

Ieee account.

  • Change Username/Password
  • Update Address

Purchase Details

  • Payment Options
  • Order History
  • View Purchased Documents

Profile Information

  • Communications Preferences
  • Profession and Education
  • Technical Interests
  • US & Canada: +1 800 678 4333
  • Worldwide: +1 732 981 0060
  • Contact & Support
  • About IEEE Xplore
  • Accessibility
  • Terms of Use
  • Nondiscrimination Policy
  • Privacy & Opting Out of Cookies

A not-for-profit organization, IEEE is the world's largest technical professional organization dedicated to advancing technology for the benefit of humanity. © Copyright 2024 IEEE - All rights reserved. Use of this web site signifies your agreement to the terms and conditions.

  • Analysis of Algorithms
  • Backtracking
  • Dynamic Programming
  • Divide and Conquer
  • Geometric Algorithms
  • Mathematical Algorithms
  • Pattern Searching
  • Bitwise Algorithms
  • Branch & Bound
  • Randomized Algorithms
  • The Role of Algorithms in Computing
  • Order of removal in Josephus problem in O(N logN)
  • Importance of Randomized Algorithms
  • Maximum number of groups of size 3 containing two type of items
  • Selection Algorithms
  • Make n using 1s and 2s with minimum number of terms multiple of k
  • Print all n-digit numbers whose sum of digits equals to given sum
  • How to check if an instance of 15 puzzle is solvable?
  • Print numbers 1 to N using Indirect recursion
  • Check if a palindromic matrix can be formed from the given array elements
  • Trabb Pardo–Knuth Algorithm
  • Minimum number of equal amount bags to collect at least M money
  • Brute Force Approach and its pros and cons
  • Fifth root of a number
  • Minimum number of page turns to get to a desired page
  • Loop Unrolling
  • Polynomial Time Approximation Scheme
  • Instance Simplification Method in Transform and Conquer Technique
  • Algorithms Design Techniques

Genetic Algorithms

Genetic Algorithms(GAs) are adaptive heuristic search algorithms that belong to the larger part of evolutionary algorithms. Genetic algorithms are based on the ideas of natural selection and genetics. These are intelligent exploitation of random searches provided with historical data to direct the search into the region of better performance in solution space. They are commonly used to generate high-quality solutions for optimization problems and search problems.

Genetic algorithms simulate the process of natural selection which means those species that can adapt to changes in their environment can survive and reproduce and go to the next generation. In simple words, they simulate “survival of the fittest” among individuals of consecutive generations to solve a problem. Each generation consists of a population of individuals and each individual represents a point in search space and possible solution. Each individual is represented as a string of character/integer/float/bits. This string is analogous to the Chromosome.

Foundation of Genetic Algorithms

Genetic algorithms are based on an analogy with the genetic structure and behavior of chromosomes of the population. Following is the foundation of GAs based on this analogy –  

  • Individuals in the population compete for resources and mate
  • Those individuals who are successful (fittest) then mate to create more offspring than others
  • Genes from the “fittest” parent propagate throughout the generation, that is sometimes parents create offspring which is better than either parent.
  • Thus each successive generation is more suited for their environment.

Search space

The population of individuals are maintained within search space. Each individual represents a solution in search space for given problem. Each individual is coded as a finite length vector (analogous to chromosome) of components. These variable components are analogous to Genes. Thus a chromosome (individual) is composed of several genes (variable components). 

genetic algorithm assignment problem

Fitness Score

A Fitness Score is given to each individual which shows the ability of an individual to “compete” . The individual having optimal fitness score (or near optimal) are sought. 

The GAs maintains the population of n individuals (chromosome/solutions) along with their fitness scores.The individuals having better fitness scores are given more chance to reproduce than others. The individuals with better fitness scores are selected who mate and produce better offspring by combining chromosomes of parents. The population size is static so the room has to be created for new arrivals. So, some individuals die and get replaced by new arrivals eventually creating new generation when all the mating opportunity of the old population is exhausted. It is hoped that over successive generations better solutions will arrive while least fit die. 

Each new generation has on average more “better genes” than the individual (solution) of previous generations. Thus each new generations have better “partial solutions” than previous generations. Once the offspring produced having no significant difference from offspring produced by previous populations, the population is converged. The algorithm is said to be converged to a set of solutions for the problem.

Operators of Genetic Algorithms

Once the initial generation is created, the algorithm evolves the generation using following operators –  1) Selection Operator: The idea is to give preference to the individuals with good fitness scores and allow them to pass their genes to successive generations.  2) Crossover Operator: This represents mating between individuals. Two individuals are selected using selection operator and crossover sites are chosen randomly. Then the genes at these crossover sites are exchanged thus creating a completely new individual (offspring). For example – 

genetic algorithm assignment problem

3) Mutation Operator: The key idea is to insert random genes in offspring to maintain the diversity in the population to avoid premature convergence. For example –   

genetic algorithm assignment problem

The whole algorithm can be summarized as –  

Example problem and solution using Genetic Algorithms

Given a target string, the goal is to produce target string starting from a random string of the same length. In the following implementation, following analogies are made – 

  • Characters A-Z, a-z, 0-9, and other special symbols are considered as genes
  • A string generated by these characters is considered as chromosome/solution/Individual

Fitness score is the number of characters which differ from characters in target string at a particular index. So individual having lower fitness value is given more preference.  

Note: Every-time algorithm start with random strings, so output may differ

As we can see from the output, our algorithm sometimes stuck at a local optimum solution, this can be further improved by updating fitness score calculation algorithm or by tweaking mutation and crossover operators.

Why use Genetic Algorithms  

  • They are Robust
  • Provide optimisation over large space state.
  • Unlike traditional AI, they do not break on slight change in input or presence of noise

Application of Genetic Algorithms

Genetic algorithms have many applications, some of them are – 

  • Recurrent Neural Network
  • Mutation testing
  • Code breaking
  • Filtering and signal processing
  • Learning fuzzy rule base etc

Please Login to comment...

  • 10 Best Free Social Media Management and Marketing Apps for Android - 2024
  • 10 Best Customer Database Software of 2024
  • How to Delete Whatsapp Business Account?
  • Discord vs Zoom: Select The Efficienct One for Virtual Meetings?
  • 30 OOPs Interview Questions and Answers (2024)

Improve your Coding Skills with Practice

 alt=

What kind of Experience do you want to share?

COMMENTS

  1. A genetic algorithm for the generalised assignment problem

    In this paper we present a genetic algorithm (GA)-based heuristic for solving the generalised assignment problem. The generalised assignment problem is the problem of finding the minimum cost assignment of n jobs to m agents such that each job is assigned to exactly one agent, subject to an agent's capacity. In addition to the standard GA procedures, our GA heuristic incorporates a problem ...

  2. An improved hybrid genetic algorithm for the generalized assignment problem

    The presented genetic algorithm with its two initialization variants is compared to the previous genetic algorithm and to the commercial general purpose branch-and-cut system CPLEX. Results indicate that CPLEX is able to solve relatively large instances of the general assignment problem to provable optimality.

  3. A hybrid genetic algorithm for three-index assignment problem

    Three-index assignment problem (AP3) is well-known problem which has been shown to be NP-hard. This problem has been studied extensively, and many exact and heuristic methods have been proposed to solve it. Inspired by the classical assignment problem, we propose a new iterative heuristic, called fragmental optimization (FO), which solves the problem by simplifying it to the assignment problem ...

  4. Genetic algorithm for the personnel assignment problem with multiple

    Genetic algorithms are proven to be very successful for NP-hard multi-objective optimization problems. In this paper, we also propose genetic algorithm solutions for different versions of the assignment problem with multiple objectives based on hierarchical and set constraints, and we empirically show the performance of these solutions.

  5. A multi-parent genetic algorithm for the quadratic assignment problem

    Instead of using traditional (two-parent) crossover operator, multi-parent crossover operator is used in genetic algorithms to improve solution quality for many numerical optimization problems. However, very few literatures are available on multi-parent crossover operator for combinatorial optimization problems, especially, quadratic assignment problem (QAP). This paper proposes a multi-parent ...

  6. PDF Solving the Assignment problem using Genetic Algorithm and Simulated

    "Assignment problem" through genetic algorithm and simulated annealing. The generalized assignment problem is basically the "N men- N jobs" problem where a single job can be assigned to only one person in such a way that the overall cost of assignment is minimized. While solving this problem through genetic algorithm

  7. [PDF] Solving Generalized Assignment Problem with Genetic Algorithm and

    An attempt has been made to solve the "Assignment problem" through genetic algorithm using an encoding scheme along with Partially Matched Crossover (PMX) function to minimize overall cost of assignment. In this paper an attempt has been made to solve the "Assignment problem" through genetic algorithm. In the assignment problem given N men and N jobs the task is to minimize overall ...

  8. Modified genetic algorithm to solve worker assignment problem with time

    The Genetic Algorithm (GA) is an effective optimization technique that has been successfully applied to a variety of optimization problems, including the Vehicle Routing Problem with Time Windows (VRPTW) by [6, 10], and general optimization benchmark problems by . GA does not exhaustively search the entire solution space but instead starts with ...

  9. A Genetic Algorithm for the Generalised Assignment Problem

    AA genetic algorithm for the generalised assignment. problem. The main steps of a GA are: Step 1: Generate a family of trial solutions; Step 2: Calculate the 'fitness' of each member of the family; Step 3: Select 'parent' solutions from the family; Step 4: Produce 'child' solutions from the 'parents'; Step 5: Calculate the 'fitness' of each ...

  10. A Genetic Algorithm for solving Quadratic Assignment Problems ...

    The Genetic Algorithm in Solving the Quadratic Assignment Problem The Quadratic Assignment Problem is one of the fundamental problems from the group of combinatorial optimization… medium.com

  11. Solving multi-class traffic assignment problem with genetic algorithm

    Based upon the mathematic characteristics of multiclass traffic assignment problem, genetic algorithm has been adopted for its solution. To ensue efficiency of the algorithm, the genetic operators such as crossover and mutation were designed specifically, as expressed by Equation 11, 12 and 13, so that constrains expressed by Equation 5 can be ...

  12. A genetic algorithm for the generalised assignment problem

    A genetic algorithm for the generalised assignment problem. John M. Wilson. Computer Science, Mathematics. 1997. A new algorithm for the generalised assignment problem is described in this paper. The algorithm is adapted from a genetic algorithm which has been successfully used on set covering problems, but….

  13. A hybrid genetic algorithm for the Three-Index Assignment Problem

    This problem has been studied extensively, and many exact and heuristic methods have been proposed to solve it. Inspired by the classical assignment problem, we propose a new local search heuristic which solves the problem by simplifying it to the classical assignment problem. We further hybridize our heuristic with the genetic algorithm (GA).

  14. Genetic Algorithm for solving Quadratic Assignment Problem (QAP)

    A Genetic Algorithm for solving Quadratic Assignment Problem (QAP) H. Azarbonyad a, R. Babazadeh b aDepartment of Electrical and computers engineering, University of Tehran, Tehran, Iran , [email protected] bDepartment of industrial engineering, University of Tehran, Tehran, Iran , [email protected] Abstract — The Quadratic Assignment Problem (QAP) is

  15. Genetic Algorithm that Solves the QAP

    The Genetic Algorithm in Solving the Quadratic Assignment Problem. The Quadratic Assignment Problem is one of the fundamental problems from the group of combinatorial optimization problems. It is ...

  16. A New Genetic Algorithm for the Quadratic Assignment Problem

    A hybrid genetic-hierarchical algorithm for the solution of the quadratic assignment problem that is combined with the so-called hierarchical (self-similar) iterated tabu search algorithm, which serves as a powerful local optimizer (local improvement algorithm) of the offspring solutions produced by the crossover operator of the genetic algorithm.

  17. Genetic Algorithm

    In this article, I am going to explain how genetic algorithm (GA) works by solving a very simple optimization problem. The idea of this note is to understand the concept of the algorithm by solving an optimization problem step by step. Let us estimate the optimal values of a and b using GA which satisfy below expression.

  18. Improved Genetic Algorithm for Weapon Target Assignment Problem

    Since the end of last century, intelligent optimization algorithm has been developing vigorously with the maturity of computer technology. Among them, genetic algorithm (GA) is the earliest and most mature optimization algorithm, and has been well applied in solving weapon target assignment (WTA) problem. In this paper, the implementation of GA is introduced. Aiming at the defect that ...

  19. Using a heuristic multi-objective genetic algorithm to solve the

    This paper proposes a CPS-based PKPS with a heuristic multi-objective genetic algorithm to solve the NP-hard storage assignment problem (SAP) for order picking operations in an e-commerce-based warehouse. The proposed algorithm considers both the workload balance between picking lines and emergency replenishment during picking operation.

  20. Genetic Algorithms

    Genetic algorithms are based on the ideas of natural selection and genetics. These are intelligent exploitation of random searches provided with historical data to direct the search into the region of better performance in solution space. They are commonly used to generate high-quality solutions for optimization problems and search problems.

  21. A Genetic Algorithm Approach to the Artillery Target Assignment Problem

    Genetic algorithm solutions with customized representations and genetic operators are developed and presented for two variations of ATAP about assigning artillery guns to targets at different time instances. In this work a new assignment problem with the name "Artillery Target Assignment Problem (ATAP)" is defined. ATAP is about assigning artillery guns to targets at different time ...