Search

This paper addresses a single-machine scheduling problem with periodic preventive maintenance activities that are predeterministic so that the machine is not available all the time, and jobs have to be processed between two consecutive maintenance periods. We propose a mixed integer programming (MIP) model and two heuristics to minimize the makespan. With more constraints in our model, the model is more efficient than the recent model of Perez-Gonzalez and Framinan , and our model could solve problems with up to fifty jobs. Two heuristic algorithms, namely, H (MW) and H (LB∗), are also proposed, in which two bin-packing policies of the minimum waste and minimum lower bound are used, respectively. Furthermore, we also proposed an improvement procedure. The results showed that the heuristic H (MW) outperformed other heuristics of the paper, indicating that the bin-packing policy of the minimum waste is more effective than well-known ones such as full batch and best fit. Additionally, all the heuristic algorithms addressed in this paper combined with the improvement procedure could achieve a similar and high quality of solutions with a very tiny increase in computational expense.

The Special Issue of Journal of Mathematical Problems in Engineering presents papers related to mixed-integer bilevel programming, bilevel stochastic control models, and combinatorial (integer programming) problems, as well as their applications to engineering/planning. J. Zhang and colleagues in 'A Unified Algorithm for Virtual Desktops Placement in Distributed Cloud Computing' make use of a multiobjective bilevel programming framework.Thena unified genetic algorithmis proposed to seek the best virtual desktops placement solution which realizes the selection of DC and the server simultaneously. C. Miao and colleagues in 'Genetic Algorithm for Mixed Integer Nonlinear Bilevel Programming and Applications in Product Family Design' study the problem in question by applying the bilevel programming (BLP) techniques. Equilibrium time-consistent strategy for corporate international investment problem with mean-variance criterion is proposed and founded in 'Equilibrium Time-Consistent Strategy for Corporate International Investment Problem with Mean-Variance Criterion' by J. Long and S. Zeng. similar stochastic-related bilevel programming problem is studied in the paper 'A Risk-Based Interval Two-Stage Programming Model for Agricultural System Management under Uncertainty' by Y. Xu and G. Huang. Another work presenting a novel aggregate production planning (APP) model for operations management is 'Enhanced Simulated Annealing for Solving Aggregate Production Planning' by M. R. Abu Bakar and colleagues.

Parallel test is an efficient approach for improving test efficiency in the aerospace field. To meet the challenges of implementing multiunit parallel test in practical projects, this paper presented a mixed-integer linear programming (MILP) model for solving the task scheduling problem. A novel sequence-based iterative (SBI) method is proposed to solve the model in reasonable time. The SBI method is composed of an implied sequence finding procedure (ISF) and a sequence-based iterative optimization (SBIO) procedure. The first procedure can reduce the search space by fixing free sequence variables according to the original test flowcharts, and the second procedure can solve the model iteratively in a reasonable amount of time. In addition, two indexes, namely, speed rate and average resource utilization rate, are introduced to evaluate the proposed methods comprehensively. Computational results indicate that the proposed method performs well in real-world test examples, especially for larger examples that cannot be solved by the full-space method. Furthermore, it is proved that the essence of the parallel test is trading space for time.

This paper presents mixed integer programming for a transportation service procurement bid construction problem from a less than full truckload perspective, in which the bidders (carriers) generate their best bid (package) using a bundled price to maximize their utility and increase the chance of winning the business. The models are developed from both the carriers and shippers perspectives to establish a relationship between the quoted price and the likelihood of winning to assist the carriers in balancing the potential benefits and the possibility of winning the bid. An intelligent algorithm based on Particle Swarm Optimization is then designed to solve the proposed model and hypothetical data sets are used to test the effectiveness and efficiency of the proposed model and algorithm.

The multiport container ship stowage problem consists in determining the position of the containers on board a ship along its route with the objective of minimizing the number of unproductive moves required in the loading and unloading operations at each port. This paper presents an integer programming model for the problem and proposes several sets of valid constraints that bring its LP-relaxation closer to an integer solution. Moreover, it presents a GRASP algorithm that generates stowage plans with a minimal number of unproductive moves in a high percentage of medium and large-size instances. An extended computational analysis has been performed in which, to the best of the authors’ knowledge, the efficiency of integer programming models for the problem is tested for the first time. With respect to GRASP, the computational results show that it performs well on different sized datasets.

In the face of rising container throughput and the tasks associated with collecting and dispatching these containers, contributions to the development of sea-rail intermodal transport are required to improve the capacity of container transportation. According to the characteristics and the requirements of the operation of sea-rail intermodal transport, this paper puts forward a design for the transport yard which facilitates container loading and unloading. Through the establishment of a mixed integer programming model, a flexible schedule for gantry crane operation can be realized, so that, during the planned period, the amount of task overflow in loading and unloading operations and the distance covered by all gantry cranes in the yard is minimized. In addition, a genetic algorithm is designed to solve this model. Finally, a specific example of the loading and unloading of a container train at the sea-rail intermodal transport yard is selected to verify the model and the algorithm. The results show that the algorithm can reasonably schedule the gantry cranes to improve their loading and unloading efficiencies in the sea-rail intermodal transport yard.

This paper studies the order acceptance and scheduling problem on unrelated parallel machines with machine eligibility constraints. Two objectives are considered to maximize total net profit and minimize the makespan, and the mathematical model of this problem is formulated as multiobjective mixed integer linear programming. Some properties with respect to the objectives are analysed, and then a classic list scheduling (LS) rule named the first available machine rule is extended, and three new LS rules are presented, which focus on the maximization of the net profit, the minimization of the makespan, and the trade-off between the two objectives, respectively. Furthermore, a list-scheduling-based multiobjective parthenogenetic algorithm (LS-MPGA) is presented with parthenogenetic operators and Pareto-ranking and selection method. Computational experiments on randomly generated instances are carried out to assess the effectiveness and efficiency of the four LS rules under the framework of LS-MPGA and discuss their application environments. Results demonstrate that the performance of the LS-MPGA developed for trade-off is superior to the other three algorithms.

It may be very difficult to achieve the optimal shift schedule in call centers which have highly uncertain and peaked demand during short time periods. Overlapping shift systems are usually designed for such cases. This paper studies shift scheduling and rostering problems for inbound call centers where overlapping shift systems are used. An integer programming model that determines which shifts to be opened and how many operators to be assigned to these shifts is proposed for the shift scheduling problem. For the rostering problem both integer programming and constraint programming models are developed to determine assignments of operators to all shifts, weekly days-off, and meal and relief break times of the operators. The proposed models are tested on real data supplied by an outsource call center and optimal results are found in an acceptable computation time. An improvement of 15% in the objective function compared to the current situation is observed with the proposed model for the shift scheduling problem. The computational performances of the proposed integer and constraint programming models for the rostering problem are compared using real data observed at a call center and simulated test instances. In addition, benchmark instances are used to compare our Constraint Programming (CP) approach with the existing models. The results of the comprehensive computational study indicate that the constraint programming model runs more efficiently than the integer programming model for the rostering problem. The originality of this research can be attributed to two contributions: (a) a model for shift scheduling problem and two models for rostering problem are presented in detail and compared using real data and (b) the rostering problem is considered as a task-resource allocation and considerably shorter computation times are obtained by modeling this new problem via CP.

When it comes to nurse shift schedules, it is found that the nursing staff have diverse preferences about shift rotations and days-off. The previous studies only focused on the most preferred work shift and the number of satisfactory days-off of the schedule at the current schedule period but had few discussions on the previous schedule periods and other preference levels for shifts and days-off, which may affect fairness of shift schedules. As a result, this paper proposes a nurse scheduling model based upon integer programming that takes into account constraints of the schedule, different preference ranks towards each shift, and the historical data of previous schedule periods to maximize the satisfaction of all the nursing staff's preferences about the shift schedule. The main contribution of the proposed model is that we consider that the nursing staff’s satisfaction level is affected by multiple preference ranks and their priority ordering to be scheduled, so that the quality of the generated shift schedule is more reasonable. Numerical results show that the planned shifts and days-off are fair and successfully meet the preferences of all the nursing staff.

In many real scheduling environments, a job processed later needs longer time than the same job when it starts earlier. This phenomenon is known as scheduling with deteriorating jobs to many industrial applications. In this paper, we study a scheduling problem of minimizing the total completion time on identical parallel machines where the processing time of a job is a step function of its starting time and a deteriorating date that is individual to all jobs. Firstly, a mixed integer programming model is presented for the problem. And then, a modified weight-combination search algorithm and a variable neighborhood search are employed to yield optimal or near-optimal schedule. To evaluate the performance of the proposed algorithms, computational experiments are performed on randomly generated test instances. Finally, computational results show that the proposed approaches obtain near-optimal solutions in a reasonable computational time even for large-sized problems.