Search

We deal with a single-machine scheduling problem with an optional maintenance activity (denoted by $ ma $), where the actual processing time of a job is a function of its starting time and position. The optional $ ma $ means that the machine will perform a $ ma $, after $ ma $ is completed, the machine will return to the initial state. The objective is to determine an optimal job sequence and the location of the maintenance activity such that makespan is to be minimized. Based on some properties of an optimal sequence, we introduce a polynomial time algorithm to solve the problem, and the time complexity is $ O({n}^4) $, where $ {n} $ is the number of jobs.

In this article, we investigate the single-machine scheduling problem with truncated learning effect and resource allocation, where the actual processing time of a job is a general function of its additional resources and position in a sequence. The goal is to determine the optimal resource allocation and optimal sequence such that a weighted sum of scheduling cost and resource consumption cost is minimized. We show that the problem can be solved in $ O(n^3) $ time by using an assignment formulation, where $ n $ is the number of jobs.

This article investigates the due-window assignment scheduling problem with setup times on a single machine, where setup times of jobs are past-sequence-dependent. Under common, slack and unrestricted due-window assignment methods, the goal is to determine the optimal job sequence and due-window such that the cost function (i.e., the weighted sum of earliness and tardiness, number of early and tardy jobs, due-window starting time and size) is minimized. We solve the problem optimally by introducing a polynomial time algorithm. An extension to the problem with learning and deterioration effects is also studied.

In practical problems, in addition to the processing time of the job, the impact of the time required for delivering the service to customers on the cost is also considered, i.e., delivery time, where the job processing time is a simple linear function of its starting time. This paper considers the impact of past-sequence-dependent delivery times (which can be referred to as psddt) on the studied objectives in three types of due windows (common, slack and different due windows). This serves to minimize the weighted sum of earliness, tardiness, starting time and size of due window, where the weights (coefficients) are related to the location. Through the theoretical analysis of the optimal solution, it is found that these three problems can be solved in time O(NlogN), respectively, where N is the number of jobs.

This paper considers the single-machine problem with job release times and flexible preventive maintenance activities to minimize total weighted tardiness, a complicated scheduling problem for which many algorithms have been proposed in the literature. However, the considered problems are rarely solved by genetic algorithms (GAs), even though it has successfully solved various complicated combinatorial optimization problems. For the problem, we propose a trajectory-based immigration strategy, where immigrant generation is based on the given information of solution extraction knowledge matrices. We embed the immigration strategy into the GA method to improve the population’s diversification process. To examine the performance of the proposed GA method, two versions of GA methods (the GA without immigration and the GA method with random immigration) and a mixed integer programming (MIP) model are also developed. Comprehensive experiments demonstrate the effectiveness of the proposed GA method by comparing the MIP model with two versions of GA methods. Overall, the proposed GA method significantly outperforms the other GA methods regarding solution quality due to the trajectory-based immigration strategy.

We tackle a new single-machine scheduling problem, whose objective is to balance the average weighted completion times of two classes of jobs. Because both the job sets contribute to the same objective function, this problem can be interpreted as a cooperative two-agent scheduling problem, in contraposition to the standard multiagent problems, which are of the competitive type since each class of job is involved only in optimizing its agent's criterion. Balancing the completion times of different sets of tasks finds application in many fields, such as in logistics for balancing the delivery times, in manufacturing for balancing the assembly lines and in services for balancing the waiting times of groups of people.To solve the problem, for which we show the NP-hardness, a Lagrangian heuristic algorithm is proposed. In particular, starting from a nonsmooth variant of the quadratic assignment problem, our approach is based on the Lagrangian relaxation of a linearized model and reduces to solve a finite sequence of successive linear assignment problems.Numerical results are presented on a set of randomly generated test problems, showing the efficiency of the proposed technique.

We consider a single-machine bi-objective scheduling problem with rejection. In this problem, it is possible to reject some jobs. Four algorithms are provided to solve this scheduling problem. The two objectives are the total weighted completion time and the total rejection cost. The aim is to determine the set of efficient solutions. Four heuristics are described; they are implicit enumeration algorithms forming a branching tree, each one having two versions according to the root of the tree corresponding either to acceptance or rejection of all the jobs. The algorithms are first illustrated by a didactic example. Then they are compared on a large set of instances of various dimension and their respective performances are analysed.

This paper studies a single-machine scheduling problem with a two competing agents in which the performance criteria of the first and second agents are to minimize the mean lateness and number of tardy jobs, respectively. Due to the non-deterministic polynomial-time hardness of this problem, we propose an effective and efficient algorithm, denominated as the SPT-M algorithm, to generate the non-dominated solutions of the Pareto set. Computational results conducted on a test problem set reveal that the proposed SPT-M algorithm can generate an efficient Pareto frontier in remarkably short computing time. The contribution of this paper could help practitioners to determine the tradeoffs between the jobs of two agents competing for a single resource.

This study evaluates various Mixed Integer Programming (MIP) formulations for solving single-machine and parallel-machine scheduling problems, with the objective of minimizing the total completion time and the makespan of jobs. Through extensive numerical study, the MIP formulation, which is suitable for dealing with each specific single-machine or parallel-machine scheduling problem, is identified. Benchmarks are also provided for the development of other algorithms for future research.

This paper analyzes a supply chain, which consists of a manufacturer, a retailer and several suppliers in which the retailer orders jobs to the manufacturer and the suppliers provide the requiring parts. The manufacturer schedules and processes the orders and dispatches them to the retailer either individually or collectively in batches. The manufacturer incurs a penalty cost for each tardy job and a transportation cost for every delivered batch and therefore, searches for a schedule that yields minimum number of tardy jobs and batches. Moreover, the manufacturer tries to optimize its supplying cost through locating the suppliers that offer appropriate release times and costs for manufacturing parts. Since the release times of parts directly affect scheduling of orders, in this research, we develop an integrated mathematical model for the manufacturer that incorporates suppliers' selection issue into the scheduling and batching decisions. Furthermore, we present a heuristic algorithm (greedy algorithm) and also a local search to quickly determine the optimal or near-optimal solutions. The computational analysis shows the importance of the integrated model and also the superiority and effectiveness of the heuristic algorithms.

This paper deals with a single-machine scheduling problem with maintenance activities. Our purpose is to provide a near optimal solution using metaheuristics approach. In this problem, there are n jobs and m machines (m≥n), each job must be assigned to one and only one machine, where the processing time of job (j) is (p_j). Furthermore there are M_G groups where each group has a fix periodic interval T and for each group, the maximum number of jobs processed in the machines available time interval (T) is K, (M_G=m/K). For finding the near optimal solution, we consider optimizing total cost scheduling problem. This problem has two types of costs, group cost and gap cost. In this study, first, proposed problem is formulated in a mathematical model. Next, a heuristic genetic algorithm is used to obtain the proposed problem and on example is presented to verify the efficiency of the algorithm.