Single-machine scheduling with learning effect and resource-dependent processing times

We consider resource allocation scheduling with learning effect in which the processing time of a job is a function of its position in a sequence and its resource allocation. The objective is to find the optimal sequence of jobs and the optimal resource allocation separately. We concentrate on two goals separately, namely, minimizing a cost function containing makespan, total completion time, total absolute differences in completion times and total resource cost; minimizing a cost function containing makespan, total waiting time, total absolute differences in waiting times and total resource cost. We analyse the problem with two different processing time functions. For each combination of these, we provide a polynomial time algorithm to find the optimal job sequence and resource allocation.     

Single-machine group scheduling with resource allocation and learning effect

This paper addresses single-machine scheduling problems under the consideration of learning effect and resource allocation in a group technology environment. In the proposed model of this paper the actual processing times of jobs depend on the job position, the group position, and the amount of resource allocated to them concurrently. Learning effect and two resource allocation functions are examined for minimizing the weighted sum of makespan and total resource cost, and the weighted sum of total completion time and total resource cost. We show that the problems for minimizing the weighted sum of makespan and total resource cost remain polynomially solvable. We also prove that the problems for minimizing the weighted sum of total completion time and total resource cost have polynomial solutions under certain conditions.     

Note on “Single-machine and flowshop scheduling with a general learning effect model” and “Some single-machine and m-machine flowshop scheduling problems with learning considerations”

In this note, we show that the main results in the two papers [C.C. Wu, W.C. Lee, Single-machine and flowshop scheduling with a general learning effect model, Computers and Industrial Engineering 56 (2009) 1553-1558, W.C. Lee, C.C. Wu, Some single-machine and m-machine flowshop scheduling problems with learning considerations, Information Sciences 179 (2009) 3885-3892] are incorrect.     

Some single-machine and m-machine flowshop scheduling problems with learning considerations

Scheduling with learning effect has drawn many researchers’ attention since Biskup [D. Biskup, Single-machine scheduling with learning considerations, European Journal of Opterational Research 115 (1999) 173-178] introduced the concept of learning into the scheduling field. Biskup [D. Biskup, A state-of-the-art review on scheduling with learning effect, European Journal of Opterational Research 188 (2008) 315-329] classified the learning approaches in the literature into two main streams. He claimed that the position-based learning seems to be a realistic model for machine learning, while the sum-of-processing-time-based learning is a model for human learning. In some realistic situations, both the machine and human learning might exist simultaneously. For example, robots with neural networks are used in computers, motor vehicles, and many assembly lines. The actions of a robot are constantly modified through self-learning in processing the jobs. On the other hand, the operators in the control center learn how to give the commands efficiently through working experience. In this paper, we propose a new learning model that unifies the two main approaches. We show that some single-machine problems and some specified flowshop problems are polynomially solvable.     

Some scheduling problems with sum-of-processing-times-based and job-position-based learning effects

In this paper we introduce a new scheduling model with learning effects in which the actual processing time of a job is a function of the total normal processing times of the jobs already processed and of the job’s scheduled position. We show that the single-machine problems to minimize makespan and total completion time are polynomially solvable. In addition, we show that the problems to minimize total weighted completion time and maximum lateness are polynomially solvable under certain agreeable conditions. Finally, we present polynomial-time optimal solutions for some special cases of the m-machine flowshop problems to minimize makespan and total completion time.     

Single-machine and flowshop scheduling with a general learning effect model

Learning effects in scheduling problems have received growing attention recently. Biskup [Biskup, D. (2008). A state-of-the-art review on scheduling with learning effect. European Journal of Operational Research, 188, 315–329] classified the learning effect scheduling models into two diverse approaches. The position-based learning model seems to be a realistic assumption for the case that the actual processing of the job is mainly machine driven, while the sum-of-processing-time-based learning model takes into account the experience the workers gain from producing the jobs. In this paper, we propose a learning model which considers both the machine and human learning effects simultaneously. We first show that the position-based learning and the sum-of-processing-time-based learning models in the literature are special cases of the proposed model. Moreover, we present the solution procedures for some single-machine and some flowshop problems.     

Minimum deviation algorithm for two-stageno-wait flowshops with parallel machines

The scheduling problems studied in this paper concern the two-stage no-wait flowshops with parallel machines under the objective function of the minimization of the maximum completion time. A new heuristic algorithm, i.e., the minimum deviation algorithm, is developed to solve the problems. In order to evaluate the average case performance of the algorithm, we design numerical experiments to compare the effectiveness of the algorithm with that of the other approximation algorithms. Extensive simulations are conducted under different shop conditions, and the results statistically show that the minimum deviation algorithm performs well under most of the situations.     

Resource-constrained flowshop scheduling with separate resource recycling operations

This paper considers the relocation problem arising from public re-development projects cast as a two-machine flowshop scheduling problem. In such a project, some buildings need to be torn down and re-constructed. The two processes of tearing down and re-constructing each building are often viewed as a single operation. However, under certain circumstances, the re-construction process, i.e., the resource recycling process, can be viewed as a separate operation. In this paper we regard these two processes as separate on the assumption that they are handled by different working crews. We formulate the problem as a resource-constrained two-machine flowshop scheduling problem with the objective of finding a feasible re-development sequence that minimizes the makespan. We provide problem formulations, discuss the complexity results, and present polynomial algorithms for various special cases of the problem.     

Flowshop scheduling of deteriorating jobs on dominating machines

In this paper we consider the general, no-wait and no-idle permutation flowshop scheduling problem with deteriorating jobs, i.e., jobs whose processing times are increasing functions of their starting times. We assume a linear deterioration function with identical increasing rates for all the jobs and there are some dominating relationships between the machines. We show that the problems to minimize the makespan and the total completion time remain polynomially solvable when deterioration is considered, although these problems are more complicated than their classical counterparts without deterioration.     

Some scheduling problems with deteriorating jobs and learning effects

Although scheduling with deteriorating jobs and learning effect has been widely investigated, scheduling research has seldom considered the two phenomena simultaneously. However, job deterioration and learning co-exist in many realistic scheduling situations. In this paper, we introduce a new scheduling model in which both job deterioration and learning exist simultaneously. The actual processing time of a job depends not only on the processing times of the jobs already processed but also on its scheduled position. For the single-machine case, we derive polynomial-time optimal solutions for the problems to minimize makespan and total completion time. In addition, we show that the problems to minimize total weighted completion time and maximum lateness are polynomially solvable under certain agreeable conditions. For the case of an m-machine permutation flowshop, we present polynomial-time optimal solutions for some special cases of the problems to minimize makespan and total completion time.     

Two-stage hybrid batching flowshop scheduling with blocking and machine availability constraints using genetic algorithm

This research investigates a two-stage hybrid flowshop scheduling problem in a metal-working company. The first stage consists of multiple parallel machines and the second stage has only one machine. Four characteristics of the company have substantiated the complexity of the problem. First, all machines in stage one are able to process multiple jobs simultaneously but the jobs must be sequentially set up one after another. Second, the setup time of each job is separated from its processing time and depends upon its preceding job. Third, a blocking environment exists between two stages with no intermediate buffer storage. Finally, machines are not continuously available due to the preventive maintenance and machine breakdown. Two types of machine unavailability, namely, deterministic case and stochastic case, are identified in this problem. The former occurs on stage-two machine with the start time and the end time known in advance. The latter occurs on one of the parallel machine in stage one and a real-time rescheduling will be triggered. Minimizing the makespan is considered as the objective to develop the optimal scheduling algorithm. A genetic algorithm is used to obtain a near-optimal solution. The computational results with actual data are favorable and superior over the results from existing manual schedules.     

Some scheduling problems with general position-dependent and time-dependent learning effects

In scheduling problems with learning effects, most of the research is based on specific learning functions. In this paper, we develop a general model with learning effects where the actual processing time of a job is not only a function of the total normal processing times of the jobs already processed, but also a function of the job’s scheduled position. In particular, it is shown that some single machine scheduling problems and m-machine permutation flowshop problems are still polynomially solvable under the proposed model. These results are significant extensions of some of the existing results on learning effects in the literature.     

Note on minimizing total tardiness in a two-machine flowshop

This note considers the problem of sequencing jobs to minimize total tardiness in a two-machine flowshop. The note shows how three dominance conditions and a lower bound previously developed for this problem can be improved. The note also proposes a new dominance condition. A branch-and-bound algorithm is developed that uses the improvements and new dominance condition. The algorithm is tested on randomly generated problems and the results of the test show that the improvements and new dominance condition improves the branch-and-bound algorithm's efficiency.     

An opportunistic resource allocation approach for mixed QoS and non-QoS connections in OFDMA wireless networks

An opportunistic resource allocation approach is proposed to guarantee both fair resource allocation and high system throughput under combinations of QoS and non-QoS connections in OFDMA networks. This approach features dynamic connection classification and packet prioritization based on real-time network conditions and QoS constraints. A classifier is first employed to prioritize QoS connections by observing the channel state of each subscriber station and the utilization of network resources. It performs a finite-horizon Markov decision process with dynamic rules affected by system load. The transmission order of packets is then determined by an opportunistic multiservice scheduler according to the QoS requirements of connections and the output of the classifier. Having the scheduling result, an allocator assigns slots to the scheduled packets, and its output is linked back to the connection classifier through a resource usage observer for all subscriber stations. The sub-channel allocation problem is also solved by cooperation between the slot allocator and the packet scheduler. Results of numerical analysis and NS2 simulation confirm the advantages claimed above. The same conclusion can also be drawn from the comparison with several existing approaches in terms of system throughput, service successful ratio, average spectral efficiency, and system revenue.     

A novel approach to resource scheduling for parallel query processing on computational grids

Advances in network technologies and the emergence of Grid computing have both increased the need and provided the infrastructure for computation and data intensive applications to run over collections of heterogeneous and autonomous nodes. In the context of database query processing, existing parallelisation techniques cannot operate well in Grid environments because the way they select machines and allocate tasks compromises partitioned parallelism. The main contribution of this paper is the proposal of a low-complexity, practical resource selection and scheduling algorithm that enables queries to employ partitioned parallelism, in order to achieve better performance in a Grid setting. The evaluation results show that the scheduler proposed outperforms current techniques without sacrificing the efficiency of resource utilisation. Recommended by: Ioannis Vlahavas     

基于任务调度的无线网贪婪信道分配算法

针对无线网络链路干扰问题,综合借鉴多处理器任务调度算法提出了一种贪婪信道分配算法,为所访问的无线网链路甄选出干扰最小的信道,并且证明了本算法的近似比率为2-1/k,其中为k为可用的正交信道数,算法复杂度为O（|E|2）。为了验证本文算法的可行性和有效性,将本文所提出的贪婪算法与随机信道分配算法和按序信道分配算法进行了实验对比。仿真结果表明：本文所提出的贪婪算法的整体性能优于其他两种算法,并且贪婪算法得到的最大干扰和平均干扰归一化值随着可用正交信道数的变化趋势较其他两种算法稳定。从而验证了本文算法能有效的降低链路干扰,一定程度上可以提升网络吞吐量。