Single-machine scheduling with learning and forgetting effects

Scheduling with learning effects has been widely studied in the past decade. With the increasingly moving toward shorter product cycle times in many production lines, workers in this changeable environment must constantly learn new skill and technology. As a result, the forgetting effect might occur in these situations. In this paper, we propose a model with the consideration of both the learning and forgetting effects. We show some single-machine problems remain polynomially solvable under the proposed model.     

Imperfect production process with learning and forgetting effects

Computational Management Science - Wright’s learning curve (WLC) assumes every unit of production has an acceptable level of quality, which is not the case in many production environments....     

Worker deployment in dual resource constrained systems with a task-type factor

This paper investigates worker learning and forgetting phenomenon in a dual resource constrained system (DRC) setting. Worker learning and forgetting in two and three stage DRC systems are modeled according to the dual-phase learning and forgetting model (DPLFM), which is based on the theory that a task has separate cognitive and motor requirements. Results show that the task-type (with respect to its learning rate and proportion of cognitive and motor requirements) affects the performance of training and deployment policies in DRC systems, and as such it should be included in future DRC research.     

Some single-machine scheduling problems with elapsed-time-based and position-based learning and forgetting effects

In this paper, a generalized model with past-sequence-dependent learning and forgetting effects is proposed. Both effects are assumed to be dependent on the sum of processing time as well as the scheduling position. Based on this model, we investigate and prove that some single-machine problems remain polynomially solvable with certain agreeable conditions. We further show that many models known in the literature are special cases of our proposed model. Several helpful lemmas are presented to analyze single-machine scheduling problems with various objective functions: makespan, total completion time, weighted completion time, and maximum lateness.     

Lead time selection and the behaviour of work flow in job shops

Few studies in job shop scheduling consider dynamic shop load and work flow issues. However, these issues are of importance to management responsible for shop floor control. This research investigates relevant internal performance measures and their relationship to external measures. As well, a new dispatching mechanism that seeks to even out the distribution of jobs in queue is investigated. Results show that a shop load balance index, which takes both shop load levels and load variability into account, has a very strong relationship to the lead times required to maintain a desired level of delivery performance. It appears that good performance based on internal measures is consistent with good performance based on external measures.     

Group scheduling problems with simultaneous considerations of learning and deterioration effects on a single-machine

Group technology is important to manufacturing as it helps increase the efficiency of production and decrease the requirement of facilities. In this paper we investigate group scheduling problems with simultaneous considerations of learning and deterioration effects on a single-machine setting. The learning phenomenon is implemented to model the setup time of groups. Three models of deteriorating for the job processing time within a group are examined. We show that all the problems studied are polynomially solvable with or without the presence of certain conditions where the objective is to find an optimal schedule for minimizing the makespan. We also investigate the minimization of the total completion time. We proved that one of the deterioration models examined in this study can also be solved in a polynomial time algorithm under certain conditions.     

Analysis of job transfer policies in systems with unreliable servers

We consider a system where incoming jobs may be executed at different servers, each of which goes through alternating periods of being available and unavailable. Neither the states of the servers nor the relevant queue sizes are known at moments of arrival. Hence, a load balancing mechanism that relies on random time-out intervals and job transfers from one queue to another is adopted. The object is to minimize a cost function which may include holding costs and transfer costs. A model of a single queue with an unreliable server and timeouts is analyzed first. The results are then used to obtain an approximate solution for arbitrary number of queues. Several transfer policies are evaluated and compared.     

Optimal threshold policies in a workload model with a variable number of service phases per job

We consider an M|E _N |1 queue in which there are two essential on-line decisions that have to be taken. The first one is the decision to either accept or reject new jobs. The second one is the decision to either continue or abort the service of a job. We show that under certain regularity conditions, there exist optimal threshold policies for these two types of decisions.     

Steady-state skill levels of workers in learning and forgetting environments: A dynamical system analysis

This article presents a study on the long-term (i.e., steady-state, convergence) characteristics of workers’ skill levels under learning and forgetting in processing units in a manufacturing environment, in which products are produced in batches. Assuming that all workers already have the basic knowledge to execute the jobs, workers learn (accumulate their skill) while producing units within a batch, forget during interruptions in production, and relearn when production resumes. The convergence properties in the paper are examined under assumptions of an infinite time horizon, a constant demand rate, and a fixed lot size. Our work extends the steady-state results of Teyarachakul, Chand, and Ward (2008) to the learning and forgetting functions that belong to a large class of functions possessing some differentiability conditions. We also discuss circumstances of manufacturing environments where our results would provide useful managerial information and other potential applications.     

Single-machine scheduling with effects of exponential learning and general deterioration

The purpose of this study is to explore the single-machine scheduling with the effects of exponential learning and general deterioration. By the effects of exponential learning and general deterioration, we meant that job processing time is decided by the functions of their starting time and positions in the sequence. Results showed that with the introduction of learning effect and deteriorating jobs to job processing time, single-machine makespan, and sum of completion time (square) minimization problems remained polynomially solvable, respectively. But for the following objective functions: the weighted sum of completion time and the maximum lateness, this paper proved that the weighted smallest basic processing time first (WSPT) rule and the earliest due date first (EDD) rule constructed the optimal sequence under some special cases, respectively.     

Technology acquisition with technological progress: effects of expectations,rivalry and uncertainty

We study the effect of expectations regarding technological progress on a firm's technology adoption decision in a duopoly. New generation technologies become available, one in each period, with successive generations representing better and better performance. A game theoretic framework is used involving two identical firms competing in the same market over two periods. It is shown that expectations retard adoption of the first period technology. It is also shown that an asymmetric equilibrium results in higher social welfare, and that more investment does not necessarily mean higher levels of welfare. Uncertainty is shown to have either no effect or a negative effect on the adoption of the current technology when Nash equilibrium holds. However, when subgame perfect equilibrium holds, uncertainty has a more complicated effect and numerical examples show that it may even encourage the adoption of the current technology relative to the deterministic equilibrium.     

Minimizing makespan in a two-machine flow shop with effects of deterioration and learning

We consider a two-machine flow shop scheduling problem with effects of deterioration and learning. By the effects of deterioration and learning, we mean that the processing time of a job is a function of its execution starting time and its position in a sequence. The objective is to find a sequence that minimizes the makespan. Several dominance properties and two lower bounds are derived, which are used to speed up the elimination process of a branch-and-bound algorithm proposed to solve the problem. Two heuristic algorithms are also proposed to obtain near-optimal solutions. Computational results are presented to evaluate the performance of the proposed algorithms.     

Scheduling in bicriteria single machine systems with past-sequence-dependent setup times and learning effects

Scheduling with setup times and learning plays a crucial role in today's manufacturing and service environments where scheduling decisions are made with respect to multiple performance criteria rather than a single criterion. In this paper, we address a bicriteria single machine scheduling problem with job-dependent past-sequence-dependent setup times and job-dependent position-based learning effects. The setup time and actual processing time of a job are respectively unique functions of the actual processing times of the already processed jobs and the position of the job in a schedule. The objective is to derive the schedule that minimizes a linear composite function of a pair of performance criteria consisting of the makespan, the total completion time, the total lateness, the total absolute differences in completion times, and the sum of earliness, tardiness, and common due date penalty. We show that the resulting problems cannot be solved in polynomial time; thus, branch-and-bound (B&B) methods are proposed to obtain the optimal schedules. Our computational results demonstrate that the B&B can solve instances of various size problems with attractive times.     

Single-machine scheduling with past-sequence-dependent setup times and general effects of deterioration and learning

Scheduling with learning effect and deteriorating jobs has become more popular. However, most of the research assume that the setup time is negligible or a part of the job processing time. In this paper, we propose a model where the deteriorating jobs, the learning effect, and the setup times are present simultaneously. Under the proposed model, the setup time is past-sequence-dependent and the actual job processing time is a general function of the processing times of the jobs already processed and its scheduled position. We provide the optimal schedules for some single-machine problems.     

Scheduling problems with past-sequence-dependent setup times and general effects of deterioration and learning

In this paper we consider the single-machine setup times scheduling with general effects of deterioration and learning. By the general effects of deterioration and learning, we mean that the actual job processing time is a general function of the processing times of the jobs already processed and its scheduled position. The setup times are proportional to the length of the already processed jobs, i.e., the setup times are past-sequence-dependent (p-s-d). We show that the problems to minimize the makespan, the sum of the δ$\delta$th (δ>0$\delta >0$) power of job completion times, the total lateness are polynomially solvable. We also show that the total weighted completion time minimization problem, the discounted total weighted completion time minimization problem, the maximum lateness (tardiness) minimization problem, the total tardiness minimization problem can be solved in polynomial time under certain conditions.     

Serial-batching scheduling with time-dependent setup time and effects of deterioration and learning on a single-machine

This paper deals with serial-batching scheduling problems with the effects of deterioration and learning, where time-dependent setup time is also considered. In the proposed scheduling models, all jobs are first partitioned into serial batches, and then all batches are processed on a single serial-batching machine. The actual job processing time is a function of its starting time and position. In addition, a setup time is required when a new batch is processed, and the setup time of the batches is time-dependent, i.e., it is a linear function of its starting time. Structural properties are derived for the problems of minimizing the makespan, the number of tardy jobs, and the maximum earliness. Then, three optimization algorithms are developed to solve them, respectively.     

Classification of subsets with minimal width and dual width in Grassmann, bilinear forms and dual polar graphs

Brouwer, Godsil, Koolen and Martin [Width and dual width of subsets in polynomial association schemes, J. Combin. Theory Ser. A 102 (2003) 255-271] introduced the width w and the dual width w^* of a subset in a distance-regular graph and in a cometric association scheme, respectively, and then derived lower bounds on these new parameters. For instance, subsets with the property w+w^*=d in a cometric distance-regular graph with diameter d attain these bounds. In this paper, we classify subsets with this property in Grassmann graphs, bilinear forms graphs and dual polar graphs. We use this information to establish the Erd?s-Ko-Rado theorem in full generality for the first two families of graphs.     

Worst-case behavior of simple sequencing rules in flow shop scheduling with general position-dependent learning effects

A real industrial production phenomenon, referred to as learning effects, has drawn increasing attention. However, most research on this issue considers only single machine problems. Motivated by this limitation, this paper considers flow shop scheduling problems with a general position-dependent learning effects. By the general position-dependent learning effects, we mean that the actual processing time of a job is defined by a general non-increasing function of its scheduled position. The objective is to minimize one of the five regular performance criteria, namely, the total completion time, the makespan, the total weighted completion time, the total weighted discounted completion time, and the sum of the quadratic job completion times. We present heuristic algorithms by using the optimal permutations for the corresponding single machine scheduling problems. We also analyze the worst-case bound of our heuristic algorithms.     

Serial-batching group scheduling with release times and the combined effects of deterioration and truncated job-dependent learning

This paper investigates a single machine serial-batching scheduling problem considering release times, setup time, and group scheduling, with the combined effects of deterioration and truncated job-dependent learning. The objective of the studied problem is to minimize the makespan. Firstly, we analyze the special case where all groups have the same arrival time, and propose the optimal structural properties on jobs sequencing, jobs batching, batches sequencing, and groups sequencing. Next, the corresponding batching rule and algorithm are developed. Based on these properties and the scheduling algorithm, we develop a hybrid VNS–ASHLO algorithm incorporating variable neighborhood search (VNS) and adaptive simplified human learning optimization (ASHLO) algorithms to solve the general case of the studied problem. Computational experiments on randomly generated instances are conducted to compare the proposed VNS–ASHLO with the algorithms of VNS, ASHLO, Simulated Annealing (SA), and Particle Swarm Optimization (PSO). The results based on instances of different scales show the effectiveness and efficiency of the proposed algorithm.     

Games as an educational resource in the teaching and learning of mathematics: an educational experiment in Portuguese middle schools

This article is based on an experiment using the game ‘Caminhando e Calculando’ (Moving and Calculating) in order to analyse the potential of the game as an educational resource for the teaching and learning of mathematics in Portuguese middle schools, where most students are 10 or 11 years old. Students' data obtained during the games will be used to analyse the different options used for solving the game, identifying its potential and its weaknesses. We start with a theoretical analysis of games as an inherent element of human culture. Combining our innate desire for fun with the different types of teaching and learning styles allows for fun and knowledge to be combined into more efficient and meaningful types of knowledge. Playing games are a primordial aspect of what it means to be a child and they develop within a motivating environment; therefore, not to take advantage of games as a learning resource would be to neglect an important asset. With regard to mathematics, emphasis will be given to the advantages that this teaching and learning tool provides for certain mathematical processes, such as problem-solving.