We examine a single machine scheduling problem with step-improving jobs in which job processing times decrease step-wisely over time according to their starting times. The objective is to minimize total completion time which is defined as the sum of completion times of jobs. The total completion time is frequently considered as an objective because it is highly related to the total time spent by jobs in the system as well as work-in-progress. Many applications of this problem can be observed in the real world such as data gathering networks, system upgrades or technological shock, and production lines operated with part-time workers in each shift. Our goal is to develop a scheduling algorithm that can provide an optimal solution. For this, we present an efficient branch and bound algorithm with an assignment-based node design and tight lower bounds that can prune branch and bound nodes at early stages and accordingly reduce the computation time. In numerical experiments well designed to consider various scenarios, it is shown that the proposed algorithm outperforms the existing method and can solve practical problems within reasonable computation time.

Determining the number of operators who set up the machines in a human-machine system is crucial for maximizing the benefits of automated production machines. A man-machine chart is an effective tool for identifying bottlenecks, improving process efficiency, and determining the optimal number of machines per operator. However, traditional man-machine charts are lacking in accounting for idle times, such as interruptions caused by other material handling equipment. We present an adjusted man-machine chart that determines the number of machines per operator, incorporating idleness as a penalty term. The adjusted man-machine chart efficiently deploys and schedules operators for the hole machining process to enhance productivity, where operators have various idle times, such as break times and waiting times by forklifts or trailers. Further, we conduct a simulation validation of traditional and proposed charts under various operational environments of operators’ fixed and flexible break times. The simulation results indicate that the adjusted man-machine chart is better suited for real-world work environments and significantly improves productivity.

This paper proposes an algorithm for the Unrelated Parallel Machine Scheduling Problem(UPMSP) without setup times, aiming to minimize total tardiness. As an NP-hard problem, the UPMSP is hard to get an optimal solution. Consequently, practical scenarios are solved by relying on operator's experiences or simple heuristic approaches. The proposed algorithm has adapted two methods: a policy network method, based on Transformer to compute the correlation between individual jobs and machines, and another method to train the network with a reinforcement learning algorithm based on the REINFORCE with Baseline algorithm. The proposed algorithm was evaluated on randomly generated problems and the results were compared with those obtained using CPLEX, as well as three scheduling algorithms. This paper confirms that the proposed algorithm outperforms the comparison algorithms, as evidenced by the test results.

Recently, scheduling problems with position-dependent processing times have received considerable attention in the literature, where the processing times of jobs are dependent on the processing sequences. However, they did not consider cases in which each processed job has different learning or aging ratios. This means that the actual processing time for a job can be determined not only by the processing sequence, but also by the learning/aging ratio, which can reflect the degree of processing difficulties in subsequent jobs. Motivated by these remarks, in this paper, we consider a two-agent single-machine scheduling problem with linear job-dependent position-based learning effects, where two agents compete to use a common single machine and each job has a different learning ratio. Specifically, we take into account two different objective functions for two agents: one agent minimizes the total weighted completion time, and the other restricts the makespan to less than an upper bound. After formally defining the problem by developing a mixed integer non-linear programming formulation, we devise a branch-and-bound (B&B) algorithm to give optimal solutions by developing four dominance properties based on a pairwise interchange comparison and four properties regarding the feasibility of a considered sequence. We suggest a lower bound to speed up the search procedure in the B&B algorithm by fathoming any non-prominent nodes. As this problem is at least NP-hard, we suggest efficient genetic algorithms using different methods to generate the initial population and two crossover operations. Computational results show that the proposed algorithms are efficient to obtain near-optimal solutions.

This paper considers a scheduling problem in a two-machine flowshop with outsourcing strategy incorporated. The jobs can be either processed in the first machine or outsourced to outside subcontractors. This paper wants to determine which jobs to be processed in-house and which jobs to be outsourced. If any job is decided to be outsourced, then an additional outsourcing cost is charged The objective of this paper is to minimize the sum of scheduling cost and outsourcing cost under a budget constraint. At first this paper characterizes some solution properties, and then it derives solution procedure including DP (Dynamic Programming) and B&B (Branch-and-Bound) algorithms and a greedy-type heuristic. Finally the performance of the algorithms are evaluated with some numerical tests.

In this paper, we deal with a single machine scheduling problems integrating with step deterioration effect and a rate-modifying activity (RMA). The scheduling problem assumes that the machine may have a single RMA and each job has the processing time of a job with deterioration is a step function of the gap between recent RMA and starting time of the job and a deteriorating date that is individual to all jobs. Based on the two scheduling phenomena, we simultaneously determine the schedule of step deteriorating jobs and the position of the RMA to minimize the makespan. To solve the problem, we propose a hybrid typed genetic algorithm compared with conventional GAs.

This paper considers a multiagent scheduling problem under public information where a machine is shared by multiple agents. Each agent has a local objective among the minimization of total completion time and the minimization of maximum. In this problem.

  This paper considers an integrated decision for scheduling and outsourcing(or, subcontracting) of a finite number of jobs(or, orders) in a time-sensitive make-to-order manufacturing environment. The jobs can be either processed in a parallel in-house fa

  This study considers the problem of scheduling jobs on uniform parallel machines with a common due date. The objective is to minimize the total absolute deviation of job completion times about the common due date. This problem is motivated by the fact t

This paper considers a single machine scheduling problem where the machine is shared by multiple sub-production systems. Each sub-production systems has heterogeneous local objectives (e.g., minimization of total completion time, maximum tardiness and makespan). In a distributed manufacturing environment, no sub-production system has complete information (e.g., processing time, due date) of the entire system. This paper provides a distributed scheduling method to find close-to-optimal coordination on the shared machine using minimum local information sharing among sub-production systems. The proposed method is compared to pareto solution that can be found in a centralized environment.

This research considers the problem of scheduling Jobs on unrelated parallel machines with a common due date The objective is to minimize the total absolute deviation of Job completion times about the common due date. This problem is motivated by the fact

게임 애플케이션에서 사용하는 데이터의 크기가 점차 커짐에 따라 물리적인 게임 서버 자원은 점차 늘어 가고 있다. 이에 따라 서버의 I/O 성능을 향상시키기 위해 게임 서버에 I/O 가상화 기술 을 도입하고자 하는 요구가 점차 증가하고 있다. 그러나, I/O 지연 시간이 수시로 변하는 게임 서버 는 I/O 응답성을 쉽게 보장하기가 힘들다. I/O 가상화 효과를 극대화하기 위해 I/O 응답성 보장은 매우 중요하며 가상 머신의 우선순위에 따라 I/O 지연 시간을 관리할 수 있는 I/O 스케줄링 기법이 반드시 필요하다. 따라서 본 논문에서는 가상화 환경에서 최대 I/O 지연 시간을 보장하는 효율적인 지연 제약 스케줄링 기법을 제안한다. 또한 제안한 기법을 이용하여 지연시간을 보장하는지 실험을 하여, 패킷의 손실량이 줄고 스케줄링의 공정성이 증가한 것을 확인하였다.