A bi-criterion single-machine scheduling problem with learning considerations

Conventionally, job processing times are assumed to be constant from the first job to be processed until the last job to be completed. However, recent empirical studies in several industries have verified that unit costs decline as firms produce more of a product and gain knowledge or experience. This phenomenon is known as the learning effect. This paper focuses on a bi-criterion single-machine scheduling problem with a learning effect. The objective is to find a sequence that minimizes a linear combination of the total completion time and the maximum tardiness. A branch-and-bound and a heuristic algorithm are proposed to search for optimal and near-optimal solutions, respectively. Computational results are also provided for the problem.Received: 21 April 2003, Accepted: 9 October 2003, Published online: 16 January 2004     

A branch-and-bound procedure for a single-machine earliness scheduling problem with two agents

This paper addresses a two-agent scheduling problem on a single machine where the objective is to minimize the total weighted earliness cost of all jobs, while keeping the earliness cost of one agent below or at a fixed level Q. A mixed-integer programming (MIP) model is first formulated to find the optimal solution which is useful for small-size problem instances. To solve medium- to large-size problem instances, a branch-and-bound algorithm incorporating with several dominance properties and a lower bound is then provided to derive the optimal solution. A simulated annealing heuristic algorithm incorporating with a heuristic procedure is developed to derive the near-optimal solutions for the problem. A computational experiment is also conducted to evaluate the performance of the proposed algorithms.     

Approximation schemes for single machine scheduling with non-renewable resource constraints

In this paper we discuss exact and approximation algorithms for scheduling a single machine with additional non-renewable resource constraints. Given the initial stock levels of some non-renewable resources (e.g., raw materials, fuel, money), and time points along with replenishment quantities, a set of resource consuming jobs has to be scheduled on the machine such that there are enough resources for starting each job, and the makespan is minimized. We show that the problem admits a pseudo-polynomial time algorithm when the number of replenishments is not part of the input, and also present an FPTAS when there is only a single resource, and it is replenished only once. We also describe a PTAS for the problem with a constant number of replenishments.     

针对资源调度问题的局部优化算法

由于现有局部搜索算法在处理数据量较大的受限资源工程调度问题时效果欠佳,提出了一种与FBI优化相结合的局部搜索方案--FBLS.FBLS利用问题的对称性,以局部搜索的解集为单位,在原问题与对称问题上交替进行优化.通过分析领域中解的合法性以及可能出现的重复情况,削减领域中解的数量,提高搜索效率.在PSPLIB的数据测试中,经FBLS优化所得到的结果已经优于所有非智能甚至大部分智能演化算法.作为一种通过局部搜索进行优化的方法,FBLS可以被灵活诮用于各种已有的智能算法框架求解RCPSP问题.     

A single-machine bi-criterion learning scheduling problem with release times

The learning effect in scheduling has received considerable attention recently. However, most researchers consider a single criterion with the assumption that jobs are all ready to be processed. The research of bi-criterion problems with learning effect is relatively limited. This paper studies a single-machine learning effect scheduling problem with release times where the objective is to minimize the sum of makespan and total completion time. First, we develop a branch-and-bound algorithm incorporating with several dominance properties and a lower bound to derive the optimal solution. Secondly, we propose a genetic algorithm to obtain near-optimal solutions. Finally, a computational experiment is conducted to evaluate the performance of the branch-and-bound and the genetic algorithms.     

Using a branch-and-bound and a genetic algorithm for a single-machine total late work scheduling problem

Scheduling with learning effects has received a lot of research attention lately. On the other hand, it is commonly seen that time restrictions are usually modeled by due dates or deadlines and the quality of schedules is estimated with reference to these parameters. One of the performance measures involving due dates is the late work criterion, which is relatively unexplored. Thus, we study a single-machine scheduling problem with a position-based learning effect. The objective is to minimize the total late work, where the late work for a job is the amount of processing of this job that is performed after its due date. We attempt to develop a branch-and-bound algorithm incorporating with some dominance rules and a lower bound for the optimal solution. For saving computational time, we also propose three heuristic-based genetic algorithms for the near-optimal solution. Finally, the computational results of proposed algorithms are also provided.     

A dynamic-programming-based exact algorithm for general single-machine scheduling with machine idle time

This paper proposes an efficient exact algorithm for the general single-machine scheduling problem where machine idle time is permitted. The algorithm is an extension of the authors’ previous algorithm for the problem without machine idle time, which is based on the SSDP (Successive Sublimation Dynamic Programming) method. We first extend our previous algorithm to the problem with machine idle time and next propose several improvements. Then, the proposed algorithm is applied to four types of single-machine scheduling problems: the total weighted earliness-tardiness problem with equal (zero) release dates, that with distinct release dates, the total weighted completion time problem with distinct release dates, and the total weighted tardiness problem with distinct release dates. Computational experiments demonstrate that our algorithm outperforms existing exact algorithms and can solve instances of the first three problems with up to 200 jobs and those of the last problem with up to 80 jobs.     

A two-agent single-machine scheduling problem with truncated sum-of-processing-times-based learning considerations

Scheduling with learning effects has received a lot of research attention lately. By learning effect, we mean that job processing times can be shortened through the repeated processing of similar tasks. On the other hand, different entities (agents) interact to perform their respective tasks, negotiating among one another for the usage of common resources over time. However, research in the multi-agent setting is relatively limited. Meanwhile, the actual processing time of a job under an uncontrolled learning effect will drop to zero precipitously as the number of jobs increases or a job with a long processing time exists. Motivated by these observations, we consider a two-agent scheduling problem in which the actual processing time of a job in a schedule is a function of the sum-of-processing-times-based learning and a control parameter of the learning function. The objective is to minimize the total weighted completion time of the jobs of the first agent with the restriction that no tardy job is allowed for the second agent. We develop a branch-and-bound and three simulated annealing algorithms to solve the problem. Computational results show that the proposed algorithms are efficient in producing near-optimal solutions.     

Ant colony algorithm for satellite control resource scheduling problem

With the increasing number of satellite, the satellite control resource scheduling problem (SCRSP) has been main challenge for satellite networks. SCRSP is a constrained and large scale combinatorial problem. More and more researches focus on how to allocate various measurement and control resources effectively to ensure the normal running of the satellites. However, the sparse solution space of SCRSP leads its complexity especially for traditional optimization algorithms. As the validity of ant colony optimization (ACO) has been shown in many combinatorial optimization problems, a simple ant colony optimization algorithm (SACO) to solve SCRSP is presented in this paper. Firstly, we give a general mathematical model of SCRSP. Then, a optimization model, called conflict construction graph, based on visible arc and working period is introduced to reduce workload of dispatchers. To meet the requirements of TT & C network and make the algorithm more practical, we make the parameters of SACO as constant, which include the bounds, update and initialization of pheromone. The effect of parameters on the algorithm performance is studied by experimental method based on SCRSP. Finally, the performance of SACO is compared with other novel ACO algorithms to show the feasibility and effectiveness of improvements.     

A study of the single-machine two-agent scheduling problem with release times

In many management situations, multiple agents compete on the usage of common processing resources. On the other hand, the importance of the ready times can be shown in Wafer fabrication with the presence of unequal ready times. It is sometimes advantageous to form a non-full batch, while in other situations it is a better strategy to wait for future job arrivals in order to increase the fullness of the batch. However, research on scheduling with two-agent and ready time simultaneously is relatively unexplored. This paper addresses a single-machine two-agent scheduling problem with ready times. The aim is to find an optimal schedule to minimize the total completion time of the jobs of the first agent with the restriction that total completion time is allowed an upper bound for the second agent. To the best of our knowledge, the problem under study has not been considered. Firstly, we show that the proposed problem is strongly NP-hard. Following that, we then develop a branch-and-bound, an ant colony, and four genetic algorithms for an optimal and near-optimal solution, respectively. In addition, the extensive computational experiments are also given.     

A single-machine scheduling problem with learning effects in intermittent batch production

This paper studies a single-machine scheduling problem with three models of learning and forgetting effects in intermittent batch production. They are the models of no transmission, partial transmission and total transmission of learning from batch to batch. The phenomena exist in many realistic production systems. The objective is to minimize the makespan. We show that the problems with the models of no transmission and partial transmission of learning from batch to batch are polynomially solvable. We also provide two polynomial time algorithms for two special cases in the problem with the total transmission model.     

An approximation algorithm for the precedence constrained scheduling problem with hierarchical communications

We study the problem of minimizing the makespan for the precedence multiprocessor constrained scheduling problem with hierarchical communications (Parallel Process. Lett. 10(1) (2000) 133). We propose an -approximation algorithm for the Unit Communication Time hierarchical problem with arbitrary but integer processing times and an unbounded number of biprocessor machines. We extend this result in the case where each cluster has m processors (where m is a fixed constant) by presenting a (2−2/(2m+1))-approximation algorithm.     

A study of single-machine scheduling problem to maximize throughput

We study inherent structural properties of a strongly NP-hard problem of scheduling $n$ jobs with release times and due dates on a single machine to minimize the number of late jobs. Our study leads to two polynomial-time algorithms. The first algorithm with the time complexity $O(n^3\log n)$ solves the problem if during its execution no job with some special property occurs. The second algorithm solves the version of the problem when all jobs have the same length. The time complexity of the latter algorithm is $O(n^2\log n)$ , which is an improvement over the earlier known algorithm with the time complexity $O(n^5)$ .     

A branch-and-bound algorithm for single-machine scheduling with batch delivery and job release times

This paper addresses scheduling a set of jobs with specified release times on a single machine for delivery in batches to customers or to other machines for further processing. This problem is a natural extension of minimizing the sum of flow times in the presence of release time by considering the possibility of delivering jobs in batches and introducing batch delivery costs. The scheduling objective adopted is that of minimizing the sum of flow times and delivery costs. The extended problem arises in the context of coordination between machine scheduling and a distribution system in a supply chain network. Structural properties of the problem are investigated and used to devise a branch-and-bound solution scheme. Computational experiments show significant improvement over an existing dynamic programming algorithm.     

A hybrid algorithm for the single-machine total tardiness problem

We propose a hybrid algorithm based on the ant colony optimization (ACO) meta-heuristic, in conjunction with four well-known elimination rules, to tackle the NP$\mathit{NP}$-hard single-machine scheduling problem to minimize the total job tardiness. The hybrid algorithm has the same running time as that of ACO. We conducted extensive computational experiments to test the performance of the hybrid algorithm and ACO. The computational results show that the hybrid algorithm can produce optimal or near-optimal solutions quickly, and its performance compares favourably with that of ACO for handling standard instances of the problem.     

Solving a two-agent single-machine scheduling problem considering learning effect

Scheduling with multiple agents and learning effect has drawn much attention. In this paper, we investigate the job scheduling problem of two agents competing for the usage of a common single machine with learning effect. The objective is to minimize the total weighted completion time of both agents with the restriction that the makespan of either agent cannot exceed an upper bound. In order to solve this problem we develop several dominance properties and a lower bound based on a branch-and-bound to find the optimal algorithm, and derive genetic algorithm based procedures for finding near-optimal solutions. The performances of the proposed algorithms are evaluated and compared via computational experiments.     

A random key based genetic algorithm for the resource constrained project scheduling problem

This paper presents a genetic algorithm for the Resource Constrained Project Scheduling Problem (RCPSP). The chromosome representation of the problem is based on random keys. The schedule is constructed using a heuristic priority rule in which the priorities of the activities are defined by the genetic algorithm. The heuristic generates parameterized active schedules. The approach was tested on a set of standard problems taken from the literature and compared with other approaches. The computational results validate the effectiveness of the proposed algorithm.     

An investigation on a two-agent single-machine scheduling problem with unequal release dates

This paper addresses a two-agent scheduling problem on a single machine with arbitrary release dates, where the objective is to minimize the tardiness of one agent, while keeping the lateness of the other agent below or at a fixed level Q. A mixed integer programming model is first presented for its optimal solution, admittedly not to be practical or useful in the most cases, but theoretically interesting since it models the problem. Thus, as an alternative, a branch-and-bound algorithm incorporating with several dominance properties and a lower bound is provided to derive the optimal solution and a marriage in honey-bees optimization algorithm (MBO) is developed to derive the near-optimal solutions for the problem. Computational results are also presented to evaluate the performance of the proposed algorithms.     

A multi-start tabu search method for a single-machine scheduling problem with periodic maintenance and sequence-dependent set-up times

In this paper we study a problem of sequencing jobs in a machine with programmed preventive maintenance and sequence-dependent set-up times. The problem combines two NP-hard problems, so we propose a heuristic method for solving it, which hybridizes multi-start strategies with Tabu Search. We compare our method with the only published metaheuristic algorithm for this problem on a set of 420 instances. The comparison favors the method developed in this work, showing that is able to find high quality solutions in very short computational times.