Article
Management
Alessandro Agnetis, Ben Hermans, Roel Leus, Salim Rostami
Summary: This paper discusses a problem of determining the state of a system through costly tests before a deadline, as well as a related search problem with multiple searchers aiming to find a target before a deadline. Both problems are shown to be NP-hard and various algorithms are proposed to tackle them effectively. Extensive computational experiments suggest that different formulations perform better in different scenarios, and a local search procedure is shown to be effective in finding near-optimal solutions.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2022)
Article
Operations Research & Management Science
Vincent T'kindt, Federico Della Croce, Mathieu Liedloff
Summary: This survey investigates the use of moderate exponential-time algorithms in NP-hard scheduling problems. It provides an overview of known results and techniques for deriving such algorithms, and discusses side topics and potential benefits.
4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH
(2022)
Article
Operations Research & Management Science
Steven J. M. den Hartog, Han Hoogeveen, Tom C. van der Zanden
Summary: This paper investigates the computational complexity of Nurse Rostering problems and shows that a problem with coverage constraints, day off requests, and forbidden sequences of shifts of length 2 is NP-hard in the strong sense, even for a small number of work shifts and a day off shift.
OPERATIONS RESEARCH LETTERS
(2023)
Article
Computer Science, Theory & Methods
Leonid A. Levin
Summary: The Gacs-Kucera theorem is an important tool in mathematics and computer science, which can reduce infinite sequences to random sequences. The early proofs of this theorem were somewhat cumbersome, but the use of general concepts can significantly simplify the proof process.
THEORETICAL COMPUTER SCIENCE
(2022)
Article
Operations Research & Management Science
Dvir Shabtay
Summary: This paper introduces two new perspectives on single-machine scheduling problems with penalties for late work, which have not been considered in previous literature. Firstly, a parameterized complexity analysis is conducted for the NP-hard problem of minimizing total late work on a single machine, considering four parameters. Secondly, two FPT algorithms are proposed to solve the problem, showing its tractability in relation to certain parameters. Furthermore, the paper explores a single-machine scheduling problem with assignable due dates and penalties for early and tardy work, providing an efficient method to assign due dates and identifying the problem's NP-hardness as well as solvability for special cases.
ANNALS OF OPERATIONS RESEARCH
(2023)
Article
Computer Science, Interdisciplinary Applications
Tianyu Wang, Igor Averbakh
Summary: The network construction/restoration problems involve finding an optimal construction schedule to minimize the total weighted recovery time or maximum lateness of vertices, which are known to be polynomially solvable on trees but NP-hard on general networks. They are also proven to be NP-hard even on simple extensions of trees like cactuses, with some polynomially solvable cases discussed.
JOURNAL OF COMBINATORIAL OPTIMIZATION
(2022)
Article
Chemistry, Multidisciplinary
Andrzej Gnatowski, Teodor Nizynski
Summary: This paper introduces a parallel algorithm and mixed integer linear programming formulation for optimizing scheduling problems in welding stations. The algorithm is optimized for modern graphics cards, with experimental results showing a speedup of up to 314 times on GPU execution compared to single-threaded CPU for sequential algorithm.
APPLIED SCIENCES-BASEL
(2021)
Article
Computer Science, Interdisciplinary Applications
Olivier Ploton, Vincent T'kindt
Summary: In this paper, a generic exact exponential algorithm is described to solve parallel machine scheduling problems with job release dates and deadlines, minimizing any general regular objective function. The algorithm has moderate exponential time complexity and pseudopolynomial space worst-case complexity bounds, enhancing the theoretical worst-case complexity bounds for various parallel machine scheduling problems.
JOURNAL OF COMBINATORIAL OPTIMIZATION
(2022)
Article
Optics
Aonan Zhang, Hao Zhan, Junjie Liao, Kaimin Zheng, Tao Jiang, Minghao Mi, Penghui Yao, Lijian Zhang
Summary: The study introduces a quantum verification machine for SAT using single photons and linear optics, which efficiently verifies SAT instances and achieves completeness-soundness gap even in the presence of experimental imperfections. The protocol is suitable for photonic realization and scalable to large problem sizes.
LIGHT-SCIENCE & APPLICATIONS
(2021)
Article
Engineering, Industrial
Wassim Zahrouni, Hichem Kamoun
Summary: This paper addresses the cyclic scheduling problem in two and three-machine robotic cells with time window constraints. It provides solutions for both cases by proving the two-machine problem can be viewed as a traveling salesman problem and proposing a heuristic for the three-machine case. The paper also presents a lower bound and reports computational results.
EUROPEAN JOURNAL OF INDUSTRIAL ENGINEERING
(2021)
Article
Operations Research & Management Science
Jan Karel Lenstra, Vitaly A. Strusevich, Milan Vlach
Summary: In 1972, Livshits and Rublinetsky published a paper in Russian where they presented linear time reductions of the partition problem to various scheduling problems. Without knowledge of complexity theory, they argued that if a simple algorithm for the partition problem was not known, then one cannot expect to find simple algorithms for these scheduling problems either. Their work did not receive much recognition, but it was not completely unnoticed. We will describe their approach and review the results.
OPERATIONS RESEARCH LETTERS
(2023)
Article
Engineering, Manufacturing
Kameng Nip, Zhenbo Wang
Summary: This study focuses on flow shop, job shop, and open shop scheduling problems under linear constraints, proposing polynomial-time optimal or approximation algorithms. It is shown that problems with processing times satisfying linear constraints are generally NP-hard in the strong sense, leading to the design of algorithms for various settings. A 2-approximation algorithm and polynomial-time approximation schemes are introduced for the general case.
JOURNAL OF SCHEDULING
(2021)
Article
Operations Research & Management Science
Philippe Chretienne
Summary: This paper explores reactive and proactive problems in single-machine scheduling, involving known baseline schedules, real job durations, and uncertain job durations. The complexity of decision problems varies depending on the specific scenario.
ANNALS OF OPERATIONS RESEARCH
(2021)
Article
Radiology, Nuclear Medicine & Medical Imaging
Laura Masi, Victor Hernandez, Jordi Saez, Raffaela Doro, Lorenzo Livi
Summary: The utility of complexity metrics for CyberKnife (CK) MLC plans was assessed in this study, adapting and computing complexity indices defined for IMRT plans. Relationships between plan complexity, optimization algorithms, and patient-specific quality assurance (PSQA) results were studied. Strong and very strong correlations were found between some pairs of complexity metrics.
Article
Engineering, Manufacturing
Yuan Zhang, Jinjiang Yuan
Summary: The study focuses on two supply chain scheduling problems aiming to minimize the total weighted number of tardy parts and the total late work of parts. Previous research claimed that both problems are unary NP-hard, but their proof was found to be invalid. The paper presents a new proof of the unary NP-hardness for the same problems.
JOURNAL OF SCHEDULING
(2021)
Article
Management
Yujing Chen, Yuanguang Zhong, T. C. E. Cheng
Summary: With the rapid development of e-commence, online shopping festivals have become increasingly important as sales drivers of online retail platforms in recent years. The selection of selling format is a key strategy for suppliers in these festivals. This study develops a model to analyze the optimal selling format selection for suppliers on online retail platforms, based on market structure and minimum quantity contract.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2023)
Article
Computer Science, Interdisciplinary Applications
Yiwei Jiang, Xuelian Tang, Kai Li, T. C. E. Cheng, Min Ji
Summary: This paper discusses the bi-objective parallel-machine scheduling problem in green manufacturing, aiming to minimize the makespan and total processing cost. For the objective of minimizing the makespan, within a given total cost budget, an approximation algorithm is proposed with a worst-case ratio of root 33+1/4, approximately equal to 1.686, which improves the previous bound of 2. For the objective of minimizing the total processing cost, subject to the constraint that all jobs must be completed before a given common deadline, an approximation algorithm is provided with a worst-case ratio of 2+r/3, where r is the ratio of the maximum to the minimum processing cost per unit time on a machine.
COMPUTERS & INDUSTRIAL ENGINEERING
(2023)
Article
Management
Ke Chen, T. C. E. Cheng, Hailiang Huang, Min Ji, Danli Yao
Summary: In this paper, the researchers investigate the impact of induced learning on due date assignment and scheduling in a manufacturing system. They discover that increasing induced learning does not decrease the number of on-time jobs, despite a potential increase in due date penalties. Based on this finding, they propose a polynomial-time algorithm that generates an approximation solution with a small gap compared to the optimal result.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2023)
Article
Management
Xiaoping Xu, Ping He, Li Zhou, T. C. E. Cheng
Summary: This study investigates the optimal decisions and coordination results of a manufacturer and an online platform in a supply chain. The cross-channel effect and blockchain technology are found to have significant impacts on the outcomes.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2023)
Article
Engineering, Industrial
Xiaoping Xu, Shunan Guo, T. C. E. Cheng, Pengcheng Du
Summary: In this paper, the authors investigate the choice of cooperation mode between an online platform and a manufacturer, where the options are reselling or agency mode. They utilize green technology to comply with a cap-and-trade scheme and meet consumers' environmental consciousness. The models take into account agency inefficiency and the inherent characteristics of e-commerce platforms. By considering three cases - agency, manufacturer-led reselling, and platform-led reselling modes - the authors analyze optimal operational decisions, platform mode choice, and coordination problems, revealing interesting findings. They find that increasing the cap weakens the optimal green level but has a mixed effect on the optimal production quantity. They also find that the platform-led reselling mode is more conducive to production quantity and green level, while the manufacturer-led reselling mode benefits the manufacturer's profit. Additionally, increasing agency inefficiency enhances market share, green level, and manufacturer's profit in the agency mode. Finally, the manufacturer-led reselling mode can coordinate the two firms.
INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS
(2023)
Article
Engineering, Industrial
Xiaoping Xu, Yuanyuan Yang, Juzhi Zhang, T. C. E. Cheng
Summary: This study examines a supply chain where a manufacturer can sell products directly or through a live streaming platform. The platform has the power to expand the market size and operates under cap-and-trade regulation. The optimal production quantity in the platform-agency mode may decrease with the cap and platform power. The supplier and manufacturer can be coordinated under the wholesale price contract in the platform-enabled mode.
INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS
(2023)
Article
Management
Peng Luo, Eric W. T. Ngai, T. C. Edwin Cheng
Summary: This study examines the relationship between supply chain network structures and firm financial performance, as well as the moderating role of international relations. The results show that network structures, such as degree, centrality, clustering coefficients, and structural holes, significantly affect firm financial performance. International relations also have a negative impact on firm financial performance, and they weaken the relationship between supply chain network structures and firm financial performance.
INTERNATIONAL JOURNAL OF OPERATIONS & PRODUCTION MANAGEMENT
(2023)
Article
Business
Hung-Pin Shih, Kee-hung Lai, T. C. E. Cheng
Summary: Confirmation biases affect consumer behavior in processing electronic word-of-mouth (eWOM), either by influencing beliefs about biased information or by creating an illusion of confidence in biased judgments. This study challenges the belief that the helpfulness of product reviews depends on unbiased information and/or judgments. Using a scenario-based questionnaire survey, the researchers found that belief consistency plays a significant role in shaping perceived review helpfulness, influenced by positive-negative asymmetry. Personal expertise may reinforce the effect of belief consistency, depending on the asymmetry between positive and negative information.
JOURNAL OF THEORETICAL AND APPLIED ELECTRONIC COMMERCE RESEARCH
(2023)
Article
Computer Science, Artificial Intelligence
Shaohua Song, Elena Tappia, Guang Song, Xianliang Shi, T. C. E. Cheng
Summary: This study aims to optimize supplier selection and demand allocation decisions for omni-channel retailers in order to achieve supply chain resilience. It proposes a two-phase approach that takes into account various factors such as supplier evaluation and demand allocation.
EXPERT SYSTEMS WITH APPLICATIONS
(2024)
Article
Engineering, Industrial
Samuel Shuai Liu, Guowei Hua, Benedict Jun Ma, T. C. E. Cheng
Summary: Blockchain technology has changed the competition between green and non-green products by certifying the green level of products. This study examines the impact of blockchain adoption on the duopoly game between green and non-green products. The results show that the green product manufacturer may not increase its price when adopting blockchain, while the non-green product manufacturer does.
INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS
(2023)
Article
Management
Yunqiang Yin, Zunhao Luo, Dujuan Wang, T. C. E. Cheng
Summary: Recent research on distributionally robust (DR) machine scheduling has explored different approaches to deal with uncertain processing times. One approach is to use statistical metrics to measure the distance between probability distributions. In this study, we focus on Wasserstein distance-based DR parallel-machine scheduling, where we minimize the worst-case expected total completion time-related cost over all distributions within a Wasserstein ambiguity set.
OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE
(2023)
Article
Psychology, Multidisciplinary
Tzu-Ling Huang, Gen-Yih Liao, T. C. E. Cheng, Wei-Xuan Chen, Ching- Teng
Summary: This study applies expectancy-value theory to examine how gaming frustration, gamers' need for achievement, and the expectation of gaming advancement jointly shape in-game achievement satisfaction and increase actual game usage. The evaluation of success probability is found to prominently determine gamers' expected value, enhancing their continued use and gameplay. The study suggests that game makers should design challenging in-game tasks that elicit hope for future achievements to keep users engaged.
COMPUTERS IN HUMAN BEHAVIOR
(2024)
Article
Geography
Pei-Chun Lin, T. C. Edwin Cheng, Chia-Hui Hsu
Summary: This study constructed a simulation model for supermarket revenue by collecting actual data and using the competing destinations model. It analyzed supermarket sales and identified suitable locations for new stores. The study provides guidance for supermarket expansion and site selection.
Article
Business
Ke Yan, Guowei Hua, T. C. E. Cheng, Tsan-Ming Choi, Jing-Xin Dong, Xinzhu Li
Summary: Cooperative promotion can enhance the competitiveness and sustainability of cross-market service platforms, but its effectiveness depends on the impact of promotional activities, price, and quality on demand, as well as their effects on profits and supply chains.
IEEE TRANSACTIONS ON ENGINEERING MANAGEMENT
(2023)
Article
Management
Ting Zhang, Tsan-Ming Choi, Tai-Chiu (Edwin) Cheng
Summary: Social comparisons during the purchase of public products can affect firms' pricing, quality, and product-line strategies. Greater social-comparison benefit reduces price competition and increases profits, while higher social-comparison cost intensifies price competition and decreases profits. Product quality differences and product-line extension strategies are also influenced by social comparisons.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2024)
Article
Computer Science, Interdisciplinary Applications
Xiaolin Wang, Liyi Zhan, Yong Zhang, Teng Fei, Ming-Lang Tseng
Summary: This study proposes an environmental cold chain logistics distribution center location model to reduce transportation costs and carbon emissions. It also introduces a hybrid arithmetic whale optimization algorithm to overcome the limitations of the conventional algorithm.
COMPUTERS & INDUSTRIAL ENGINEERING
(2024)
Article
Computer Science, Interdisciplinary Applications
Hong-yu Liu, Shou-feng Ji, Yuan-yuan Ji
Summary: This study proposes an architecture that utilizes Ethereum to investigate the production-inventory-delivery problem in Physical Internet (PI), and develops an iterative heuristic algorithm that outperforms other algorithms. However, due to gas prices and consumption, blockchain technology may not always be the optimal solution.
COMPUTERS & INDUSTRIAL ENGINEERING
(2024)
Article
Computer Science, Interdisciplinary Applications
Paraskevi Th. Zacharia, Elias K. Xidias, Andreas C. Nearchou
Summary: This article discusses the assembly line balancing problem in production lines with collaborative robots. Collaborative robots have the potential to improve automation, productivity, accuracy, and flexibility in manufacturing. The article explores the use of a problem-specific metaheuristic to solve this complex problem under uncertainty.
COMPUTERS & INDUSTRIAL ENGINEERING
(2024)
