## 1 Introduction  
The job-shop scheduling problem (JSSP) is a well-known and highly studied problem in operations research, with applications spanning manufacturing, services, logistics, and many other domains [1, 2]. It is considered one of the most challenging combinatorial optimization problems due to its NP-hard nature and the complexity introduced by real-world constraints. Most traditional studies on JSSP assume constant machine efficiency and often overlook maintenance activities [3, 4, 5]. These assumptions simplify the problem for theoretical exploration, though they fail to represent real-world scenarios where machine efficiency can vary over time due to factors like wear and tear, usage patterns, and environmental conditions [6]. Similarly, maintenance activities, critical for ensuring machine longevity and operational efficiency, impose additional constraints on job scheduling by requiring planned downtime [7]. This paper addresses these limitations by introducing a new problem variant: the job-shop scheduling problem with variable machine efficiency and maintenance activities (JSSP-VME-MT). Unlike classical JSSP, the JSSP-VME-MT incorporates dynamic machine efficiency, which affects job processing times, and maintenance activities that restore machine efficiency. Specifically, this study examines a linearly decaying efficiency model where machine performance diminishes over time and is periodically restored through voluntary maintenance of constant duration. By integrating these realistic factors, the JSSP-VME-MT bridges the gap between theoretical models and practical scheduling applications. The complexity of JSSP-VME-MT necessitates advanced solution methodologies capable of balancing global exploration and local exploitation. Evolutionary algorithms (EAs), known for their robustness and flexibility, are widely used to solve complex scheduling problems [8; 9; 10]. EAs draw inspiration from natural evolution, employing selection, crossover, and mutation operations to evolve populations of candidate solutions. Their strength lies in global search capabilities, allowing exploration of diverse regions in the solution space. However, while EAs are effective for global exploration, they often lack the refinement necessary for local optimization. Local search algorithms excel in thoroughly exploiting the vicinity of a given solution [11; 12; 13]. By systematically investigating neighboring solutions, these algorithms enhance solution quality through fine-tuning. This complementary behavior highlights the potential of combining global exploration with local exploitation for solving complex scheduling problems like JSSP-VME-MT. To leverage the strengths of both paradigms, this paper adopts a memetic algorithm (MA) as the solution framework. Memetic algorithms (MAs) are hybrid metaheuristics that integrate local search procedures within the framework of evolutionary algorithms [14; 15; 16]. This synergy enables MAs to maintain a diverse population of solutions while intensively searching promising regions for refinement. Such a balance is particularly effective for tackling JSSP-VME-MT, as it addresses the multifaceted challenges of variable machine efficiency and maintenance planning. In this study, we contribute to the literature by (1) defining the JSSP-VME-MT problem, (2) developing a novel encoding scheme to represent both job sequencing and maintenance activities, and (3) implementing a memetic algorithm that combines global search and local refinement techniques. Experimental results demonstrate the effectiveness of this approach, achieving significant reductions in makespan while accounting for realistic constraints. This work lays the foundation for future research in scheduling problems involving dynamic machine performance and planned maintenance activities. The paper is structured as follows. Section 2 reviews the related literature on job-shop scheduling problems and the integration of machine efficiency and maintenance activities.